Tìm kiếm chi phí đều

Trong khoa học máy tính, tìm kiếm chi phí đều (hay còn gọi là tìm kiếm chi phí cực tiểu hoặc tìm kiếm theo giá thành thống nhất, viết tắt tiếng AnhUCS) là một cách duyệt cây dùng cho việc duyệt hay tìm kiếm một cây, cấu trúc cây, hoặc đồ thị có trọng lượng (chi phí). Việc tìm kiếm bắt đầu tại nút gốc.[1] Việc tìm kiếm tiếp tục bằng cách duyệt các nút tiếp theo với trọng lượng hay chi phí thấp nhất tính từ nút gốc. Các nút được duyệt tiếp tục cho đến khi đến được nút đích cần đến.

Thuật toán

procedure UniformCostSearch(Graph, root, goal)
 node:= root, cost = 0
 frontier:= priority queue containing node only
 explored:= empty set
 do
if frontier is empty
 return failure
node:= frontier.pop()
if node is goal
 return solution
explored.add(node)
for each of node's neighbors n
 if n is not in explored
  if n is not in frontier
 frontier.add(n)
  else if n is in frontier with higher cost
 replace existing node with n

Ví dụ

Mở rộng các tập đã xét và hàng đợi ưu tiên:
Nút bắt đầu: A
Nút kết thúc: G

Các bước Biên giới: tập các đối tượng (nút và chi phí) Mở rộng[*] Đã xét: tập các nút đã xét
1 {(A,0)} A
2 {(D,3),(B,5)} D {A}
3 {(B,5),(E,5),(F,5)} B {A,D}
4 {(E,5),(F,5),(C,6)} E {A,D,B}
5 {(F,5),(C,6)}[**] F {A,D,B,E}
6 {(C,6),(G,8)} C {A,D,B,E,F}
7 {(G,8)} G {A,D,B,E,F,C}
8

^ * Nút được chọn để duyệt cho bước tiếp theo.
^ ** B không được thêm vào hàng đợi vì nó đã nằm trong tập đã xét.
Đường đi được tìm thấy: A -> D -> F -> G. Ở bước số 3, các nút B, E, F đều có chi phí là 5, trường hợp này có thể chọn 1 nút bất kỳ hoặc ưu tiên theo thứ tự các nút (chẳng hạn như theo thứ tự chữ cái B, E, F thì chọn B).

Tham khảo

  1. ^ Uniform Cost Search Lưu trữ 2013-10-29 tại Wayback Machine, Đại học Stanford.

Liên kết ngoài

Read other articles:

Cari artikel bahasa  Cari berdasarkan kode ISO 639 (Uji coba)  Kolom pencarian ini hanya didukung oleh beberapa antarmuka Halaman bahasa acak Bahasa Neo-Latin Neolatina edisi pertama dari Systema Naturae, yakni Linnaeus, merupakan salah satu teks Neo-Latin paling terkenal WilayahDunia BaratEraDari masa Petrarca dan Latin Renaisans pada abad ke-14, puncaknya pada 1500–1700; penggunaan masa kini sebagai Latin Kontemporer Rumpun bahasaIndo-Eropa ItalikLatino-FaliskiLatinNeo-Latin Ben...

 

46 Leonis Minoris Lokasi dari 46 Leonis Minoris (dilingkari) Data pengamatan Epos J2000      Ekuinoks J2000 Rasi bintang Leo Minor Asensio rekta  10j 53m 18.70487d Deklinasi  +34° 12′ 53.5375″ Magnitudo tampak (V) 3.83 Ciri-ciri Kelas spektrum K0+ III-IV[1] AstrometriGerak diri (μ) RA: +92.02 mdb/thn Dek.: –285.82 mdb/thn Paralaks (π)34,38±0,21 mdbJarak94,9 ± 0,6 tc (29...

 

Poster di Manchukuo yang menggambarkan hubungan harmonis antara orang Jepang, orang Han, dan orang Manchu. Slogan di bawahnya berbunyi: Perdamaian dunia berkat kerja sama Jepang, Tiongkok, dan Manchukuo. Gambar anak di sebelah kanan yang memegang bendera Lima Bangsa Dalam Satu Perserikatan yang melambangkan Tiongkok. Propaganda di kekaisaran Jepang, pada periode tepat sebelum dan saat Perang Dunia II, dirnacang untuk membantu pemerintahan Jepang yang berkuasa pada masa itu. Sebagian besar uns...

American activist (born 1941) Linda JennessSocialist Workers candidate forPresident of the United StatesRunning mateAndrew PulleyOpponent(s)Richard Nixon (R)George McGovern (D)John Hospers (Libertarian)John G. Schmitz (AI)Benjamin Spock (People's)IncumbentRichard Nixon (R) Personal detailsBorn1941 (age 82–83)Atlanta, Georgia, U.S.Political partySocialist Workers Linda Jenness (born January 11, 1941)[1] is a former Socialist Workers Party candidate for president of the Unit...

 

Insiden 28 JanuariBagian dari the Perang Tiongkok-Jepang KeduaTanggal28 Januari – 3 Maret 1932LokasiShanghai, TiongkokHasil Gencatan senjata; demiliterisasi ShanghaiPihak terlibat Republik Tiongkok  Empire of Japan Kekaisaran JepangTokoh dan pemimpin 19th Route Army: Jiang Guangnai (Chinese: 蔣光鼐), 5th Army: Zhang Zhizhong (Chinese: 張治中) Commander: Yoshinori Shirakawa (白川義則code: ja is deprecated ), Chief of staff: Kanichiro Tashiro (田代皖一郎code: ja is depreca...

 

Bilateral relationsKenya–United Kingdom relations Kenya United Kingdom Diplomatic missionHigh Commission of Kenya, LondonBritish High Commission, NairobiEnvoyHigh Commissioner Manoah EsipisuHigh Commissioner Jane Marriott Kenya–United Kingdom relations are bilateral relations between Kenya and the United Kingdom. The interactions between the two states have been positive and friendly since Kenya's independence in 1963.[1][2] Both the UK and Kenya are members of the Commonw...

Island in Hong Kong For similar terms, see Ma Wan (painter) and Ma Wan (Tung Chung). This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Ma Wan – news · newspapers · books · scholar · JSTOR (September 2007) (Learn how and when to remove this template message) Ma Wan馬灣General view of Ma Wan from the northLoca...

 

Disambiguazione – Se stai cercando altri significati, vedi Finlandia (disambigua). Finlandia (dettagli) (dettagli) Finlandia - LocalizzazioneLa Finlandia (verde scuro) nell'Unione europea (verde chiaro) Dati amministrativiNome completoRepubblica di Finlandia Nome ufficiale(FI) Suomen tasavalta(SV) Republiken Finland Lingue ufficialiFinlandese, Svedese[1] Altre linguesami, romaní e suomalainen viittomakieli[2] Capitale Helsinki  (648 650 ab. / 2018)...

 

Dora RipariaLa Dora Riparia a CondoveStato Italia Lunghezza101,093 km[1][2] Portata media27,8 m³/s[3] Bacino idrografico1 340,26 km²[4] Altitudine sorgente~ 2 500[5] m s.l.m. Nascetra monte Chenaillet e monte Gimont (Montgenèvre)[5] SfociaPo a Torino 45°04′42.68″N 7°43′27.17″E / 45.078522°N 7.724214°E45.078522; 7.724214Coordinate: 45°04′42.68″N 7°43′27.17″E / 45.078522°N 7....

Natalie HembyInformasi latar belakangNama lahirNatalie Nicole HembyLahir24 Maret 1977 (umur 47)Puxico, Missouri, Amerika Serikat[1]AsalNashville, Tennessee, Amerika SerikatGenreCountry, musik folk, penyanyi-penulis laguPekerjaanPenulis lagu, penyanyiTahun aktifakhir 2000an-kiniArtis terkaitThe Highwomen Natalie Nicole Hemby Wrucke (lahir 24 Maret 1977) adalah seorang penulis lagu dan penyanyi musik country Amerika Serikat. Ia menulis lagu-lagu untuk Lee Ann Womack, Eli Young Band...

 

American politician (1772–1851) For his grandson, see Benjamin W. Crowninshield. Benjamin Williams CrowninshieldMember of the U.S. House of Representativesfrom Massachusetts's 2nd districtIn officeMarch 4, 1823 – March 3, 1831Preceded byGideon BarstowSucceeded byRufus Choate5th United States Secretary of the NavyIn officeJanuary 16, 1815 – September 30, 1818PresidentJames MadisonJames MonroePreceded byWilliam JonesSucceeded bySmith Thompson Personal details...

 

Mappa delle Orcadi La Saga degli uomini delle Orcadi o Orkneyinga saga è una popolare saga norrena che tratta della storia della conquista dell'arcipelago scozzese delle Orcadi da parte dei Norvegesi (IX secolo) e della successiva epoca dei conti delle Orcadi che si concluse nel XII secolo). La saga è scritta in norreno e presenta numerosi prestiti onomastici da altre lingue, specialmente dall'area celto-gaelica, come per esempio Frakökk e Maddaðr. La saga è stata redatta in un'epoca com...

Герб Филиппин Детали Утверждён 1940 Девиз Republika ng Pilipinas  Медиафайлы на Викискладе Герб Филиппин был принят в 1940 году. Это щит с солнцем Филиппин посередине, 8 лучей которого представляют 8 областей (Батангас, Булакан, Кавите, Манила, Лагуна, Нуэва Эсиха, Пампанга и Тарлак); т�...

 

Japan Template‑class Japan portalThis template is within the scope of WikiProject Japan, a collaborative effort to improve the coverage of Japan-related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the project, participate in relevant discussions, and see lists of open tasks. Current time in Japan: 18:55, May 11, 2024 (JST, Reiwa 6) (Refresh)JapanWikipedia:WikiProject JapanTemplate:WikiProject JapanJapan-related articlesTemplate...

 

Roman Catholic military order founded by crusaders around 1119 This article is about the medieval Catholic military order. For its successor, see Order of Saints Maurice and Lazarus. For other uses, see Order of Saint Lazarus (disambiguation). For the society of apostolic life also known as Lazarists, see Congregation of the Mission. Order of Saint Lazarus of JerusalemFlag of the orderSuccessorOrder of Saints Maurice and Lazarus (Italian branch, since 1572)Order of Our Lady of Mount Carmel an...

Susanoo atau Takehaya Susanoo-no-Mikoto, populer disebut Susanoo-no-Mikoto, adalah dewa laut dan petir menurut mitologi Shinto.[1] Catatan tentang Susanoo tertulis di buku Kojiki pada tahun 680 M dan 720 M di buku Nihongi.[2] Lukisan Susanoo yang bertarung melawan Yamata-no-Orochi. Mitologi menurut Kojiki dan Nihongi Menurut kisah yang ditulis Kojiki, dia terlahir dari basuhan air hidung Izanagi ketika mensucikan diri sepulang dari neraka.[1][2] Tetapi, menurut...

 

English country house in Hertfordshire For the English contract law case and Wrotham Park damages, see Wrotham Park Estate Co Ltd v Parkside Homes Ltd. Wrotham ParkWrotham Park in 1820location within HertfordshireGeneral informationTypeEnglish country houseArchitectural styleNeo-PalladianLocationNear Potters Bar, HertfordshireCountryEnglandCoordinates51°40′38″N 0°11′48″W / 51.67722°N 0.19667°W / 51.67722; -0.19667Completed1754Destroyed1883 (fire), then rebu...

 

American cuisine variant New York–style pizza, the original pizza in the United States Pizza arrived in the United States in the early 20th century along with waves of Italian immigrants who settled primarily in the larger cities of the Northeast, such as New York, Philadelphia, Boston and Baltimore. After American soldiers stationed in Italy returned from World War II, pizza and pizzerias rapidly grew in popularity.[1] During the latter half of the 20th century, pizza became an ico...

Japanese railway company For other uses, see Hankyu (disambiguation). This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Hankyu – news · newspapers · books · scholar · JSTOR (September 2015) (Learn how and when to remove this message) Hankyu RailwaySix-track section near Umeda terminal; Nakatsu Station in the c...

 

Not to be confused with Operator (mathematics). Addition, multiplication, division, ... Elementary arithmetic operations:+, plus (addition)−, minus (subtraction)÷, obelus (division)×, times (multiplication) In mathematics, an operation is a function which takes zero or more input values (also called operands or arguments) to a well-defined output value. The number of operands is the arity of the operation. The most commonly studied operations are binary operations (i.e., operations of ari...