Wikipedia Algoritma pathfinding A * membutuhkan banyak waktu

9

Saya telah berhasil mengimplementasikan A * pathfinding di C # tetapi sangat lambat, dan saya tidak mengerti mengapa. Saya bahkan mencoba untuk tidak menyortir daftar openNodes tetapi masih sama.

Peta ini 80x80, dan ada 10-11 node.

Saya mengambil pseudocode dari sini Wikipedia

Dan ini adalah implementasi saya:

 public static List<PGNode> Pathfind(PGMap mMap, PGNode mStart, PGNode mEnd)
    {
        mMap.ClearNodes();

        mMap.GetTile(mStart.X, mStart.Y).Value = 0;
        mMap.GetTile(mEnd.X, mEnd.Y).Value = 0;

        List<PGNode> openNodes = new List<PGNode>();
        List<PGNode> closedNodes = new List<PGNode>();
        List<PGNode> solutionNodes = new List<PGNode>();

        mStart.G = 0;
        mStart.H = GetManhattanHeuristic(mStart, mEnd);

        solutionNodes.Add(mStart);
        solutionNodes.Add(mEnd);

        openNodes.Add(mStart); // 1) Add the starting square (or node) to the open list.

        while (openNodes.Count > 0) // 2) Repeat the following:
        {
            openNodes.Sort((p1, p2) => p1.F.CompareTo(p2.F));

            PGNode current = openNodes[0]; // a) We refer to this as the current square.)

            if (current == mEnd)
            {
                while (current != null)
                {
                    solutionNodes.Add(current);
                    current = current.Parent;
                }

                return solutionNodes;
            }

            openNodes.Remove(current);
            closedNodes.Add(current); // b) Switch it to the closed list.

            List<PGNode> neighborNodes = current.GetNeighborNodes();
            double cost = 0;
            bool isCostBetter = false;

            for (int i = 0; i < neighborNodes.Count; i++)
            {
                PGNode neighbor = neighborNodes[i];
                cost = current.G + 10;
                isCostBetter = false;

                if (neighbor.Passable == false || closedNodes.Contains(neighbor))
                    continue; // If it is not walkable or if it is on the closed list, ignore it.

                if (openNodes.Contains(neighbor) == false)
                {
                    openNodes.Add(neighbor); // If it isn’t on the open list, add it to the open list.
                    isCostBetter = true;
                }
                else if (cost < neighbor.G)
                {
                    isCostBetter = true;
                }

                if (isCostBetter)
                {
                    neighbor.Parent = current; //  Make the current square the parent of this square. 
                    neighbor.G = cost;
                    neighbor.H = GetManhattanHeuristic(current, neighbor);
                }
            }
        }

        return null;
    }

Inilah heuristik yang saya gunakan:

    private static double GetManhattanHeuristic(PGNode mStart, PGNode mEnd)
    {
        return Math.Abs(mStart.X - mEnd.X) + Math.Abs(mStart.Y - mEnd.Y);
    }

Apa yang saya lakukan salah? Ini sepanjang hari saya terus mencari kode yang sama.

Vee
sumber
2
Tanpa heuristik (biasanya) akan memakan waktu lebih lama ketika Anda melewati lebih banyak node sampai Anda menemukan akhirnya. Juga, coba gunakan daftar yang diurutkan yang tetap diurutkan (lebih disukai satu set yang diurutkan, dengan begitu Anda tidak perlu memeriksa apakah ada item dalam daftar yang bisa Anda tambahkan)
Elva

Jawaban:

10

Saya melihat tiga hal, satu salah, dua mencurigakan.

1) Anda sedang mengurutkan pada setiap iterasi. Jangan. Baik gunakan antrian prioritas, atau paling tidak lakukan pencarian linier untuk menemukan minimum. Anda sebenarnya tidak perlu seluruh daftar untuk disortir setiap saat!

2) openNodes.Contains () mungkin lambat (tidak yakin tentang spesifikasi Daftar C #, tapi saya yakin itu melakukan pencarian linear). Anda dapat menambahkan flag ke setiap node dan melakukan ini di O (1).

3) GetNeighborNodes () bisa lambat.

ggambett
sumber
2
2) Ya, Berisi () akan sangat lambat. Daripada menyimpan semua node Anda dalam daftar, gunakan Kamus <int, PGNode>. Maka Anda mendapatkan O (1) waktu pencarian dan masih bisa mengulang daftar daftar. Jika node memiliki bidang id, gunakan itu untuk kunci, jika tidak PGNode.GetHashCode () akan berfungsi.
Lenensi
2
@Lenfficiency: Bukankah Kamus <PGNode, PGNode> lebih baik? Dua objek mungkin memiliki kode hash yang sama tetapi tidak sama. "Akibatnya, implementasi default metode ini tidak boleh digunakan sebagai pengidentifikasi objek unik untuk tujuan hashing." msdn.microsoft.com/en-us/library/system.object.gethashcode.aspx - .NET 3.5 menyediakan HashSet, yang lebih baik - msdn.microsoft.com/en-us/library/bb359438.aspx .
Poin bagus, lupakan HashSet.
Lenfficiency
9

Selain poin yang sudah dibuat bahwa Anda harus menggunakan tumpukan prioritas, Anda telah salah memahami heuristik. Kamu punya

if (isCostBetter)
{
    ...
    neighbor.H = GetManhattanHeuristic (saat ini, tetangga);
}
Tapi heuristik itu seharusnya menjadi perkiraan untuk jarak ke tujuan. Anda harus mengaturnya sekali, saat pertama kali menambahkan tetangga:
if (openNodes.Contains (neighbor) == false)
{
    neighbor.H = GetHeuristic (tetangga, mEnd);
    ...
}

Dan sebagai titik minor lebih lanjut, Anda dapat menyederhanakan A * dengan memfilter simpul yang tidak dapat dilewati GetNeighbourNodes().

Peter Taylor
sumber
+1, saya fokus pada kompleksitas algoritmik dan sepenuhnya melewatkan penggunaan heuristik yang salah!
ggambett
4

Meta-jawaban: Anda tidak boleh hanya menghabiskan waktu sehari menatap kode mencari masalah kinerja. Lima menit dengan profiler akan menunjukkan dengan tepat di mana letak hambatannya. Anda dapat mengunduh jejak gratis sebagian besar profiler dan menghubungkannya ke aplikasi Anda dalam beberapa menit.

banyak sekali
sumber
3

Tidak jelas apa yang Anda bandingkan ketika Anda membandingkan F dari node yang berbeda. Apakah F properti didefinisikan sebagai G + H? Harus. (Kata-kata kasar: Ini adalah contoh mengapa prinsip akses seragam adalah omong kosong.)

Lebih penting lagi, Anda menyortir ulang node setiap frame. A * panggilan untuk penggunaan antrian prioritas , yang memungkinkan efisien - O (lg n) - diurutkan penyisipan elemen tunggal, dan satu set, yang memungkinkan pemeriksaan cepat untuk node tertutup. Saat Anda telah menulis algoritme, Anda memiliki penyisipan + O (n lg n), yang menaikkan run-time ke proporsi yang tidak berguna.

(Anda mungkin mendapatkan O (n) penyisipan + urutkan jika C # memiliki algoritma penyortiran yang baik. Itu masih terlalu banyak. Gunakan antrian prioritas nyata.)


sumber
2

http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html

  • Pada satu ekstrim, jika h (n) adalah 0, maka hanya g (n) yang berperan, dan A * berubah menjadi algoritma Dijkstra, yang dijamin untuk menemukan jalur terpendek.
  • Jika h (n) selalu lebih rendah dari (atau sama dengan) biaya pindah dari n ke tujuan, maka A * dijamin untuk menemukan jalur terpendek. Semakin rendah h (n), semakin banyak simpul A * mengembang, membuatnya lebih lambat.
  • Jika h (n) persis sama dengan biaya bergerak dari n ke tujuan, maka A * hanya akan mengikuti jalur terbaik dan tidak pernah memperluas apa pun, membuatnya sangat cepat. Meskipun Anda tidak dapat membuat ini terjadi dalam semua kasus, Anda dapat membuatnya tepat dalam beberapa kasus khusus. Sangat menyenangkan mengetahui bahwa dengan informasi yang sempurna, A * akan berperilaku sempurna.
  • Jika h (n) kadang-kadang lebih besar daripada biaya bergerak dari n ke tujuan, maka A * tidak dijamin untuk menemukan jalur terpendek, tetapi dapat berjalan lebih cepat.
  • Di sisi lain, jika h (n) sangat tinggi relatif terhadap g (n), maka hanya h (n) yang berperan, dan A * berubah menjadi Best-First-Search.

Anda menggunakan 'jarak manhatten'. Ini hampir selalu heuristik yang buruk. Selain itu, dari melihat info itu dari halaman tertaut, Anda dapat menebak bahwa heuristik Anda lebih rendah dari biaya sebenarnya.

Akan
sumber
-1, masalahnya bukan heuristik, tetapi implementasinya.
2

Selain jawaban teratas lainnya (yang tidak diragukan lagi lebih penting daripada saran ini), optimasi lain adalah mengubah 'daftar' yang tertutup menjadi semacam tabel hash. Anda tidak perlu menjadi koleksi yang dipesan, hanya untuk dapat dengan cepat menambah nilai dan melihat dengan cepat apakah ada dalam koleksi.

Kylotan
sumber
1

Biaya Anda dan Heuristik Anda perlu memiliki hubungan. Ini harus menjadi petunjuk bahwa H dihitung di dua tempat yang berbeda tetapi tidak pernah diakses.

Jay Bell
sumber
Ini mengasumsikan properti diimplementasikan secara tidak benar, yang dimungkinkan karena definisinya tidak ditampilkan, tetapi ada dua masalah langsung dengan kode.