Пошук А* - Історія редагувань

111: /* Застосування пошуку A * */

2018-02-21T20:45:42Z

‎Застосування пошуку A *

111: /* Пошук A . Реалізація. /

2018-02-21T17:07:59Z

‎Пошук A *. Реалізація.

111: /* Пошук А.Загально /

2018-02-21T12:40:04Z

‎Пошук А*.Загально

111: /* Застосування пошуку A * */

2018-02-21T12:37:17Z

‎Застосування пошуку A *

111: /* Застосування пошуку A * */

2018-02-21T12:35:41Z

‎Застосування пошуку A *

111: /* Застосування пошуку A * */

2018-02-21T12:35:15Z

‎Застосування пошуку A *

111: /* Пошук A * і Загадка Восьми */

2018-02-21T12:34:41Z

‎Пошук A * і Загадка Восьми

111: /* Пошук А* */

2018-02-21T12:33:31Z

‎Пошук А*

111 в 12:32, 21 лютого 2018

2018-02-21T12:32:56Z

111: /* Пошук A . Реалізація. /

2018-02-21T12:31:27Z

‎Пошук A *. Реалізація.

← Попередня версія		Версія за 20:45, 21 лютого 2018
Рядок 152:		Рядок 152:
	Пошук A * є популярною технікою та використовується як алгоритм визначення шляху для комп'ютерних стратегічних ігор. Для більшої продуктивності в багатьох іграх застосовуються більш прості способи швидкого пошуку шляху, обмежуючи простір їх переміщення (використовуючи набагато розріджений графік по ландшафту) або попередньо розраховуючи маршрути для використання в грі.		Пошук A * є популярною технікою та використовується як алгоритм визначення шляху для комп'ютерних стратегічних ігор. Для більшої продуктивності в багатьох іграх застосовуються більш прості способи швидкого пошуку шляху, обмежуючи простір їх переміщення (використовуючи набагато розріджений графік по ландшафту) або попередньо розраховуючи маршрути для використання в грі.

−	Виконала [[~~User:~~Назаренко Валерія\|Назаренко Валерія]]	+
		+	Виконала [[Назаренко Валерія \|Назаренко Валерія]]

@@ Рядок 85: / Рядок 85: @@
 Тут ми включаємо параметри альфа та бета, щоб дати різну вагу для значень g та h. У цій реалізації альфа - 1,0, бета - 2,0. Це означає, що більша вага надається значенням h, а згодом, чим ближче до цілі вузол, він зважується вище його глибини в дереві стану.
- Коли обчислено значення f, ми перевіряємо, чи знаходиться вузол у списку OPEN. Якщо це так, ми порівнюємо їх значення f. Якщо вузол у списку OPEN має гірше значення f, вузол у списку OPEN відкидається, а новий дочірній вузол займає своє місце (встановивши посилання попередника на предка, тому ми знаємо, як ми перейшли до цього вузла). Якщо вузол у списку OPEN має краще значення f, то вузол у списку OPEN залишається у відкритому списку, а новий дочірній вузол відкидається.
+Коли обчислено значення f, ми перевіряємо, чи знаходиться вузол у списку OPEN. Якщо це так, ми порівнюємо їх значення f. Якщо вузол у списку OPEN має гірше значення f, вузол у списку OPEN відкидається, а новий дочірній вузол займає своє місце (встановивши посилання попередника на предка, тому ми знаємо, як ми перейшли до цього вузла). Якщо вузол у списку OPEN має краще значення f, то вузол у списку OPEN залишається у відкритому списку, а новий дочірній вузол відкидається.
 Нарешті, якщо новий дочірній вузол не існує ні в списку ЗАКРИТО, ні в OPEN, це новий вузол, який ми ще маємо побачити. Він просто додається до списку OPEN, і процес триває.
 Цей алгоритм продовжується до тих пір, поки не відбудеться одне з двох подій. Якщо список OPEN стає порожнім, то не знайдено жодного рішення, а алгоритм завершується. Якщо рішення знайдено, викликається showSolution, а вузли, з'єднані між собою через посилання попередника, перераховуються, щоб показати рішення від вихідного вузла до цільового вузла.

← Попередня версія		Версія за 12:40, 21 лютого 2018
Рядок 1:		Рядок 1:
−	== Пошук А*.Загально ==	+	== Пошук А*. Загально ==

	Пошук А, як і[[ ПОШУК «НАЙКРАЩИЙ-ПЕРШИЙ» (BEST-FS) \|«найкращий-перший» пошук]], оцінює простір пошуку за допомогою евристичної функції. Але A використовує як вартість отримання від початкового стану до поточного стану (g (n)), так і оцінювану вартість (евристичну) шляху від поточного вузла до мети (h (n)). Вони підсумовуються до функції витрат f (n). Пошук A *, на відміну від першого, є оптимальним і повним.		Пошук А, як і[[ ПОШУК «НАЙКРАЩИЙ-ПЕРШИЙ» (BEST-FS) \|«найкращий-перший» пошук]], оцінює простір пошуку за допомогою евристичної функції. Але A використовує як вартість отримання від початкового стану до поточного стану (g (n)), так і оцінювану вартість (евристичну) шляху від поточного вузла до мети (h (n)). Вони підсумовуються до функції витрат f (n). Пошук A *, на відміну від першого, є оптимальним і повним.

@@ Рядок 151: / Рядок 151: @@
 == Застосування пошуку A * ==
 Пошук  A *  є популярною технікою та використовується як алгоритм визначення шляху для комп'ютерних стратегічних ігор. Для більшої продуктивності в багатьох іграх застосовуються більш прості способи швидкого пошуку шляху, обмежуючи простір їх переміщення (використовуючи набагато розріджений графік по ландшафту) або попередньо розраховуючи маршрути для використання в грі.
-Виконала
-----
+Виконала [[User:Назаренко Валерія|Назаренко Валерія]]
 Назаренко Валерія

@@ Рядок 151: / Рядок 151: @@
 == Застосування пошуку A * ==
 Пошук  A *  є популярною технікою та використовується як алгоритм визначення шляху для комп'ютерних стратегічних ігор. Для більшої продуктивності в багатьох іграх застосовуються більш прості способи швидкого пошуку шляху, обмежуючи простір їх переміщення (використовуючи набагато розріджений графік по ландшафту) або попередньо розраховуючи маршрути для використання в грі.
-Виконала --[[Користувач:111|111]] ([[Обговорення користувача:111|обговорення]]) 14:35, 21 лютого 2018 (EET)Назаренко Валерія
+Виконала

← Попередня версія		Версія за 12:35, 21 лютого 2018
Рядок 151:		Рядок 151:
	== Застосування пошуку A * ==		== Застосування пошуку A * ==
	Пошук A * є популярною технікою та використовується як алгоритм визначення шляху для комп'ютерних стратегічних ігор. Для більшої продуктивності в багатьох іграх застосовуються більш прості способи швидкого пошуку шляху, обмежуючи простір їх переміщення (використовуючи набагато розріджений графік по ландшафту) або попередньо розраховуючи маршрути для використання в грі.		Пошук A * є популярною технікою та використовується як алгоритм визначення шляху для комп'ютерних стратегічних ігор. Для більшої продуктивності в багатьох іграх застосовуються більш прості способи швидкого пошуку шляху, обмежуючи простір їх переміщення (використовуючи набагато розріджений графік по ландшафту) або попередньо розраховуючи маршрути для використання в грі.
		+	Виконала --[[Користувач:111\|111]] ([[Обговорення користувача:111\|обговорення]]) 14:35, 21 лютого 2018 (EET)Назаренко Валерія

@@ Рядок 43: / Рядок 43: @@
 == Пошук  A * і Загадка Восьми ==
-Хоча A * успішно застосовується до проблемних доменів, таких як конфігурація, ми застосуємо його тут, що називається "Загадка восьми" (також відомий як N від M, або n^2-1 загадка черпиць).  Ця особлива варіація головоломки складається з восьми черепиць в сітці 3х3. В одному місці немає плитки, що можна використовувати для переміщення інших плиток для переходу від однієї конфігурації до іншої (див. Малюнок 3.4).
+Хоча A * успішно застосовується до проблемних доменів, таких як конфігурація, ми застосуємо його тут, що називається [[Загадка Восьми|"Загадка Восьми"]] (також відомий як N від M, або n^2-1 загадка черпиць).  Ця особлива варіація головоломки складається з восьми черепиць в сітці 3х3. В одному місці немає плитки, що можна використовувати для переміщення інших плиток для переходу від однієї конфігурації до іншої (див. Малюнок 3.4).
 [[Файл:34.png]]
-Малюнок 3.4: Задача Восьми та демонстрація переходу з вхідної конфігурації до кінцевої (не включає кожен єтап).
+''Малюнок 3.4: Задача Восьми та демонстрація переходу з вхідної конфігурації до кінцевої (не включає кожен єтап).''
 Зверніть увагу на малюнку 3.4, що є можливі дві дії. Плитка '1' може рухатися вліво, а плитка '6' може рухатися вниз. Остаточна мета конфігурації показана справа. Зауважте, що це один варіант мети, і той, який ми будемо використовувати тут.

← Попередня версія		Версія за 12:33, 21 лютого 2018
Рядок 1:		Рядок 1:
−	== Пошук А* ==	+	== Пошук А*.Загально ==

	Пошук А, як і[[ ПОШУК «НАЙКРАЩИЙ-ПЕРШИЙ» (BEST-FS) \|«найкращий-перший» пошук]], оцінює простір пошуку за допомогою евристичної функції. Але A використовує як вартість отримання від початкового стану до поточного стану (g (n)), так і оцінювану вартість (евристичну) шляху від поточного вузла до мети (h (n)). Вони підсумовуються до функції витрат f (n). Пошук A *, на відміну від першого, є оптимальним і повним.		Пошук А, як і[[ ПОШУК «НАЙКРАЩИЙ-ПЕРШИЙ» (BEST-FS) \|«найкращий-перший» пошук]], оцінює простір пошуку за допомогою евристичної функції. Але A використовує як вартість отримання від початкового стану до поточного стану (g (n)), так і оцінювану вартість (евристичну) шляху від поточного вузла до мети (h (n)). Вони підсумовуються до функції витрат f (n). Пошук A *, на відміну від першого, є оптимальним і повним.

← Попередня версія		Версія за 12:32, 21 лютого 2018
Рядок 1:		Рядок 1:
		+	== Пошук А* ==
		+
	Пошук А, як і[[ ПОШУК «НАЙКРАЩИЙ-ПЕРШИЙ» (BEST-FS) \|«найкращий-перший» пошук]], оцінює простір пошуку за допомогою евристичної функції. Але A використовує як вартість отримання від початкового стану до поточного стану (g (n)), так і оцінювану вартість (евристичну) шляху від поточного вузла до мети (h (n)). Вони підсумовуються до функції витрат f (n). Пошук A *, на відміну від першого, є оптимальним і повним.		Пошук А, як і[[ ПОШУК «НАЙКРАЩИЙ-ПЕРШИЙ» (BEST-FS) \|«найкращий-перший» пошук]], оцінює простір пошуку за допомогою евристичної функції. Але A використовує як вартість отримання від початкового стану до поточного стану (g (n)), так і оцінювану вартість (евристичну) шляху від поточного вузла до мети (h (n)). Вони підсумовуються до функції витрат f (n). Пошук A *, на відміну від першого, є оптимальним і повним.

@@ Рядок 80: / Рядок 80: @@
 За допомогою нового дочірнього вузла ми перевіряємо, чи вона вже була оцінена (якщо вона знаходиться в списку CLOSED). Якщо це так, ми повинні знищити цей вузол і продовжувати (щоб отримати дочірній вузол для поточної конфігурації дошки). Якщо ми раніше не бачили цю конкретну конфігурацію дошки, ми обчислюємо евристику для вузла. По-перше, ми ініціалізуємо глибину вузла в дереві як глибину предка плюс один. Далі, ми викликаємо evaluateBoard, щоб отримати метрику, що виходить за межі плитки, яка буде діяти як наша значення h (вартість від кореневого вузла до цього вузла). Значення g встановлюється на поточну глибину, а значення f ініціалізується за допомогою рівняння.
-[[Файл:56.jpg]]
+[[Файл:56.png]]
 Тут ми включаємо параметри альфа та бета, щоб дати різну вагу для значень g та h. У цій реалізації альфа - 1,0, бета - 2,0. Це означає, що більша вага надається значенням h, а згодом, чим ближче до цілі вузол, він зважується вище його глибини в дереві стану.
@@ Рядок 144: / Рядок 144: @@
+  }
- ==A * варіанти==
+== A * варіанти ==
 Популярність A * породила ряд варіантів, які пропонують різні характеристики. Алгоритм Ітеративне-поглиблення A * відступає до інших вузлів, коли вартість поточної гілки перевищує порогове значення. Щоб мінімізувати вимоги до пам'яті A *, було створено алгоритм спрощеного алгоритму A *, обмежений пам'яттю (SMA *). SMA * використовує доступну для нього пам'ять, і коли він виходить за межі доступної пам'яті, алгоритм знижує найменш перспективний вузол, щоб полегшити нові пошукові вузли з нової області.
-  ==Застосування пошуку A *==
+== Застосування пошуку A * ==
 Пошук  A *  є популярною технікою та використовується як алгоритм визначення шляху для комп'ютерних стратегічних ігор. Для більшої продуктивності в багатьох іграх застосовуються більш прості способи швидкого пошуку шляху, обмежуючи простір їх переміщення (використовуючи набагато розріджений графік по ландшафту) або попередньо розраховуючи маршрути для використання в грі.

Пошук А* - Історія редагувань

111: /* Застосування пошуку A * */

111: /* Пошук A *. Реалізація. */

111: /* Пошук А*.Загально */

111: /* Застосування пошуку A * */

111: /* Застосування пошуку A * */

111: /* Застосування пошуку A * */

111: /* Пошук A * і Загадка Восьми */

111: /* Пошук А* */

111 в 12:32, 21 лютого 2018

111: /* Пошук A *. Реалізація. */

111: /* Пошук A . Реалізація. /

111: /* Пошук А.Загально /

111: /* Пошук A . Реалізація. /