Загадка Восьми - Історія редагувань

111: /* Демонстрація Загадки Восьми з пошуком A . /

2018-02-21T20:46:03Z

‎Демонстрація Загадки Восьми з пошуком A *.

111: /* Уявлення Загадки Восьми */

2018-02-21T19:47:36Z

‎Уявлення Загадки Восьми

111: /* Загадка Восьми */

2018-02-21T19:46:38Z

‎Загадка Восьми

111: /* Загадка Восьми */

2018-02-21T17:18:07Z

‎Загадка Восьми

111: /* Уявлення Загадки Восьми */

2018-02-21T17:10:44Z

‎Уявлення Загадки Восьми

111: /* Загадка Восьми */

2018-02-21T17:09:41Z

‎Загадка Восьми

111: Створена сторінка: == Загадка Восьми == Файл:34.jpg ''Малюнок 3.4: Задача Восьми та демонстрація переходу з вхі...

2018-02-21T17:02:38Z

Створена сторінка: == Загадка Восьми == Файл:34.jpg ''Малюнок 3.4: Задача Восьми та демонстрація переходу з вхі...

Нова сторінка

== Загадка Восьми ==

[[Файл:34.jpg]]

''Малюнок 3.4: Задача Восьми та демонстрація переходу з вхідної конфігурації до кінцевої (не включає кожен єтап).''

Хоча A * успішно застосовується до проблемних доменів, таких як конфігурація, ми застосуємо його тут, що називається [[Загадка Восьми |"Загадка восьми"]] (також відомий як N від M, або n^2-1 загадка черпиць). Ця особлива варіація головоломки складається з восьми черепиць в сітці 3х3. В одному місці немає плитки, що можна використовувати для переміщення інших плиток для переходу від однієї конфігурації до іншої (див. Малюнок 3.4).
Зверніть увагу на малюнку 3.4, що є можливі дві дії. Плитка '1' може рухатися вліво, а плитка '6' може рухатися вниз. Остаточна мета конфігурації показана справа. Зауважте, що це один варіант мети, і той, який ми будемо використовувати тут.
[[Загадка Восьми |Загадка Восьми]]- це цікаво, тому що важко вирішити проблему, але та, що вивчається довго, і тому дуже добре зрозуміла. [Archer 1999] Наприклад, кількість можливих конфігурацій сітки Загадки Восьми (n * n)!, але лише половина з них є легальними конфігураціями.
''Підказка
У 1870-х роках Загадка П'ятнадцяти (4 на 4 варіанти головоломки N по M) перетворилися на загальне захоплення так само, як кубик Рубіка 1970-х та 80-х років.''

У середньому 22 кроки потрібні для вирішення 3-х варіантів головоломки. Але, розглядаючи 22 як середню глибину дерева, із середнім коефіцієнтом розгалуження 2,67, може бути оцінено 2,4 трильйони не унікальних плиток.

== Уявлення Загадки Восьми ==

Ми будемо використовувати загальне уявлення для Загадки Восьми, лінійний вектор, що містить розташування черепиці зліва направо, зверху вниз (див. Малюнок 3.5). Ця конкретна фігура показує можливі рухи від початкової конфігурації головоломки до другої глибини цього конкретного дерева символів структури.

[[Файл:67.png]]

Для нашого евристичного методу ми будемо використовувати глибину дерева як вартість від кореневого до поточного вузла (інакше як g (n)), а також кількість неправильних плиток (h (n)) як оцінювану вартість для цільового вузла (крім порожнього). Вартість шляху (f (n)) потім стає вартістю шляху до поточного вузла (g (n)) плюс приблизна вартість цільового вузла (h (n)). Ви можете побачити ці евристики в дереві на малюнку 3.6. З кореневого вузла можливі лише два рухи, але з цих двох рухів відкриваються три нових ходи (стани). У нижній частині цього дерева ви можете побачити, що функція витрат зменшилася, що вказує на те, що ці конфігурації плану, швидше за все, будуть кандидатами для вивчення далі.
''ПРИМІТКА
Існує дві популярні евристики для проблеми N-головоломки. Перше - це просто кількість плиток, які не використовуються, що загалом зменшується, коли наближається ціль.
Інший евристичний - це відстань Манхеттена від плитки, яка підсумовує відстань між черепицею кожної місцевої плитки та її правильному розташуванню. Для цієї реалізації ми продемонструємо просту, але ефективну елітарну схему.''

[[Файл:99.png]]
''Малюнок 3.6: Дерево Загадки Восьми завершуеться на другій глибині, ілюстрування функцій вартості. ''
''Порада
Хоча є (3 * 3)! можливі конфігурації плати, є лише (3 * 3)! / 2 дійсних конфігурацій. Інша половина конфігурацій нерозв'язна. Ми не зупинимося на цьому тут, але в реалізації джерела ви побачите тест у initPuzzle, використовуючи поняття інверсій для перевірки конфігурації плати. Цю концепцію можна детальніше дослідити в [KGong 2005].''

== Демонстрація Загадки Восьми з пошуком A *. ==

У процесі виконання плитки позначаються як A-H з пробілом, який використовується для позначення порожньої плитки. Після виконання, коли знайдено рішення, перераховується шлях, знятий з початкової плати до мети. Це показано нижче в нонатці, мінімізоване для простору.

'''Нотатка: Зразок програми А* для вирішення Загадки Восьми.'''

$./astar
GBD
FCH
EA
BGD
FCH
E A
BGD
FCH
EA
GBD
FC
EAH
...
ABC
DF
GEH
ABC
D F
GEH
ABC
DEF
G H
ABC
DEF
GH

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

← Попередня версія		Версія за 20:46, 21 лютого 2018
Рядок 68:		Рядок 68:
	GH		GH

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

@@ Рядок 23: / Рядок 23: @@
 Для нашого евристичного методу ми будемо використовувати глибину дерева як вартість від кореневого до поточного вузла (інакше як g (n)), а також кількість неправильних плиток (h (n)) як оцінювану вартість для цільового вузла (крім порожнього). Вартість шляху (f (n)) потім стає вартістю шляху до поточного вузла (g (n)) плюс приблизна вартість цільового вузла (h (n)). Ви можете побачити ці евристики в дереві на малюнку 3.6. З кореневого вузла можливі лише два рухи, але з цих двох рухів відкриваються три нових ходи (стани). У нижній частині цього дерева ви можете побачити, що функція витрат зменшилася, що вказує на те, що ці конфігурації плану, швидше за все, будуть кандидатами для вивчення далі.
 ''ПРИМІТКА
 Існує дві популярні евристики для проблеми N-головоломки. Перше - це просто кількість плиток, які не використовуються, що загалом зменшується, коли наближається ціль.
@@ Рядок 30: / Рядок 31: @@
 ''Малюнок 3.6: Дерево Загадки Восьми завершуеться на другій глибині, ілюстрування функцій вартості. ''
 ''Порада
 Хоча є (3 * 3)! можливі конфігурації плати, є лише (3 * 3)! / 2 дійсних конфігурацій. Інша половина конфігурацій нерозв'язна. Ми не зупинимося на цьому тут, але в реалізації джерела ви побачите тест у initPuzzle, використовуючи поняття інверсій для перевірки конфігурації плати. Цю концепцію можна детальніше дослідити в [KGong 2005].''

← Попередня версія		Версія за 19:46, 21 лютого 2018
Рядок 8:		Рядок 8:

	Зверніть увагу на малюнку 3.4, що є можливі дві дії. Плитка '1' може рухатися вліво, а плитка '6' може рухатися вниз. Остаточна мета конфігурації показана справа. Зауважте, що це один варіант мети, і той, який ми будемо використовувати тут.		Зверніть увагу на малюнку 3.4, що є можливі дві дії. Плитка '1' може рухатися вліво, а плитка '6' може рухатися вниз. Остаточна мета конфігурації показана справа. Зауважте, що це один варіант мети, і той, який ми будемо використовувати тут.
		+
	[[Загадка Восьми \|Загадка Восьми]]- це цікаво, тому що важко вирішити проблему, але та, що вивчається довго, і тому дуже добре зрозуміла. [Archer 1999] Наприклад, кількість можливих конфігурацій сітки Загадки Восьми (n * n)!, але лише половина з них є легальними конфігураціями.		[[Загадка Восьми \|Загадка Восьми]]- це цікаво, тому що важко вирішити проблему, але та, що вивчається довго, і тому дуже добре зрозуміла. [Archer 1999] Наприклад, кількість можливих конфігурацій сітки Загадки Восьми (n * n)!, але лише половина з них є легальними конфігураціями.

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

@@ Рядок 1: / Рядок 1: @@
 == Загадка Восьми ==
-[[Файл:34.jpg]]
+[[Файл:34.png]]
 ''Малюнок 3.4: Задача Восьми та демонстрація переходу з вхідної конфігурації до кінцевої (не включає кожен єтап).''

Загадка Восьми - Історія редагувань

111: /* Демонстрація Загадки Восьми з пошуком A *. */

111: /* Уявлення Загадки Восьми */

111: /* Загадка Восьми */

111: /* Загадка Восьми */

111: /* Уявлення Загадки Восьми */

111: /* Загадка Восьми */

111: Створена сторінка: == Загадка Восьми == Файл:34.jpg ''Малюнок 3.4: Задача Восьми та демонстрація переходу з вхі...

111: /* Демонстрація Загадки Восьми з пошуком A . /