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 Anh là UCS) 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:

Bahasa Neo-Latin

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

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...

 

Propaganda di Jepang pada Perang Tiongkok-Jepang Kedua dan Perang Dunia II

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...

Linda Jenness

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 Januari

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...

 

Kenya–United Kingdom relations

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...

Ma Wan

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...

 

Finlandia

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 Riparia

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 Hemby

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...

 

Benjamin Williams Crowninshield

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...

 

Saga degli uomini delle Orcadi

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 областей (Батангас, Булакан, Кавите, Манила, Лагуна, Нуэва Эсиха, Пампанга и Тарлак); т�...

 

Template talk:Hidaka

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...

 

Order of Saint Lazarus

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

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...

 

Wrotham Park

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...

 

Pizza in the United States

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...

Hankyu

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...

 

Operation (mathematics)

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...