Од шуналтай юу?

2024 Зохиолч: Lynn Donovan | [email protected]. Хамгийн сүүлд өөрчлөгдсөн: 2023-12-15 23:50

А*(А од ) A* нь Dijkstra ба хоёрын хослол юм Шуналтай . Энэ нь үндсэн зангилаа хүртэлх зай болон зорилго хүртэлх эвристик зайг ашигладаг. Зорилгын цэгийг олох үед алгоритм дуусна.

Мөн шунахай нь хамгийн сайн эхний хайлтыг дуусгасан уу?

Дүгнэж хэлэхэд, шуналтай BFS тийм биш бүрэн , үгүй оновчтой , O(bm) цагийн нарийн төвөгтэй, олон гишүүнт байж болох орон зайн нарийн төвөгтэй. А* байна бүрэн , оновчтой , мөн энэ нь O(bm) цаг ба орон зайн нарийн төвөгтэй байдаг. Тэгэхээр, ерөнхийдөө, A* илүү санах ой ашигладаг шуналтай BFS. үед A* хэрэгжих боломжгүй болно хайх орон зай асар том.

Дээрх хажууд * зөвшөөрөгдөх үү? Хэрэв эвристик функц бол зөвшөөрөгдөх , энэ нь зорилгодоо хүрэх бодит зардлыг хэзээ ч хэтрүүлдэггүй гэсэн үг, A* нь эхлэлээс зорилго хүртэл хамгийн бага зардалтай замыг буцаах баталгаатай. Зорилгын f утга нь хамгийн богино замын зардал болно, учир нь зорилгод хүрэх h нь an-д тэг байна зөвшөөрөгдөх эвристик.

Түүгээр ч барахгүй, яагаад * нь хамгийн сайн анхны хайлтаас дээр вэ?

А* хүрдэг илүү сайн чиглүүлэхийн тулд эвристикийг ашиглан гүйцэтгэл хайх . A* нь давуу талыг хослуулсан Хамгийн сайн - анхны хайлт ба нэгдмэл зардал Хайх : эвристик ашиглан алгоритмын үр ашгийг нэмэгдүүлэхийн зэрэгцээ оновчтой замыг олохыг баталгаажуулна.

A * алгоритм дууссан уу?

А* байна бүрэн хэрэв байгаа бол үргэлж шийдлийг олох болно. Википедиагийн нийтлэлийг харна уу. Цаашид эвристик нь зөвшөөрөгдөх бөгөөд монотон байвал алгоритм мөн зөвшөөрөгдөх болно (өөрөөр хэлбэл оновчтой).