Поиск в глубину

@alena05 · Регистрация: 21.12.2012

Студворк — интернет-сервис помощи студентам

Здравствуйте! Мне задали реализовать алгоритм ограниченного поиска в глубину без повторов и применить его для игры "8" (аналог пятнашек размерности 3*3 с числами от 1 до 8 и пустой клеткой). Насколько я поняла, необходимо воспользоваться уже описанным у Вас алгоритмом - Поиск в пространстве состояний (поиск по графам тоже сюда!), поиск с итерационным заглублением. Но как его модифицировать я не могу понять=(. Помогите пожалуйста, заранее спасибо.

Добавлено через 21 час 35 минут
Насколько я понимаю, дожна быть функция move([X1,X2,X3,X4,X5,0,X6,X7,X8]) и перебрать перестановки для разных вариантов расположения пустой клетки, правильно?

@Грымзик · 22.12.2012, 23:03

Да, правильно. Например сдвиг влево

Prolog
1
2
3
4
5
m(State1,State2):-
     append(Begin,[0,X|Tail],State1),
     length(Begin,Len),
     Len\=2,Len\=5,
     append(Begin,[X,0|Tail],State2).

@alena05 · 23.12.2012, 15:35 **[ТС]**

Не получается что-то рабочее сделать(((((
А зачем надо Len \=2 и Len\=5?
И еще, в описанном случае можно сразу напсать

Prolog
1
2
3
4
5
6
m(State1,State2):-
     append(Begin,[0,X|Tail],State1),
     length(Begin,Len),
     Len\=2,Len\=5,
     append(Begin,[X,0|Tail],State2);
     append(Begin,[X,X,X,X,0|Tail],State2).

- добавления смещения вниз?

Добавлено через 13 минут
Точнее

Prolog
1
append(Begin,[X,X,X,0|Tail],State2)

последняя строка, один X лишний

@Грымзик · 24.12.2012, 20:17

Операция ИЛИ имеет меньший приоритет, чем И, поэтому подобную конструкцию надо брать в скобки

Prolog
1
2
3
...
     (append(Begin,[X,0|Tail],State2);
     append(Begin,[X,X,X,X,0|Tail],State2)).

Переменная может принимать только одно значение, поэтому
[X,X,X,X,0|Tail] не сработает в данной задаче никогда.

Сообщение от alena05

А зачем надо Len \=2 и Len\=5?

Потому что без этого условия можно будет сдвинуть 4ю клетку на 3ю,
что явно в действительности невозможно. И при сдвиге вверх про это
не надо будет забывать.

@alena05 · 24.12.2012, 21:21 **[ТС]**

Сообщение от Грымзик

Потому что без этого условия можно будет сдвинуть 4ю клетку на 3ю,
что явно в действительности невозможно. И при сдвиге вверх про это
не надо будет забывать.

Т.Е именно это надо добавлять в каждое условие?

@Грымзик · 24.12.2012, 21:55

Нет, не именно это. Подумайте сами, нарисуйте поле, и посмотрите в каких случаях недопустимо вверх передвинуть.

@alena05 · 03.01.2013, 12:22 **[ТС]**

А этот код остается без изменений(кроме замени имени move)?

Prolog
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
prolong([Temp|Tail],[New,Temp|Tail]):-
        move(Temp,New),not(member(New,[Temp|Tail])).
 
int(1).
int(N):-int(M),N is M+1.
 
search_id(Start,Finish):-
    int(Level),(Level>100,!;id([Start],Finish,Way,Level),show_answer(Way)).
 
id([Finish|Tail],Finish,[Finish|Tail],0).
id(TempWay,Finish,Way,N):-N>0,
    prolong(TempWay,NewWay),N1 is N-1,
    id(NewWay,Finish,Way,N1).
 
show_answer([_]):-!.
show_answer([A,B|Tail]):-
        show_answer([B|Tail]),nl,write(B),write(' -> '),write(A).

Все выходные промучиласьничего не работает=(
Буду очень благодарна, если бы Вы написалинесколько ходов

@alena05 · 08.01.2013, 08:58 **[ТС]**

Все работает,спасибо огромное

Добавлено через 5 часов 17 минут
Только при нерешаемых комбинацияхпроисходит зацикливание

@Грымзик · 08.01.2013, 14:13

В Level>100 поменяйте 100 на число поменьше.

Новые блоги и статьи Все статьи Все блоги /
Автозаполнение реквизита при выборе элемента справочника Maks 27.03.2026 Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. При выборе "Спецтехники" (Тип Справочник. Спецтехника), заполняется. . .	Сумматор с применением элементов трёх состояний. Hrethgir 26.03.2026 Тут. https:/ / fips. ru/ EGD/ ab3c85c8-836d-4866-871b-c2f0c5d77fbc Первый документ красиво выглядит, но без схемы. Это конечно не даёт никаких плюсов автору, но тем не менее. . . всё может быть. . .	Автозаполнение реквизитов при создании документа Maks 26.03.2026 Программный код из решения ниже размещается в модуле объекта документа, в процедуре "ПриСозданииНаСервере". Алгоритм проверки заполнения реализован для исключения перезаписи значения реквизита,. . .	Команды формы и диалоговое окно Maks 26.03.2026 1. Команда формы "ЗаполнитьЗапчасти". Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. В качестве источника данных. . .
Кому нужен AOT? DevAlt 26.03.2026 Решил сделать простой ланчер Написал заготовку: dotnet new console --aot -o UrlHandler var items = args. Split(":"); var tag = items; var id = items; var executable = args;. . .	Отправка уведомления на почту при создании или изменении элементов справочника Maks 24.03.2026 Программная отправка письма электронной почты на примере типового справочника "Склады" в конфигурации БП3. Перед реализацией необходимо выполнить настройку системной учетной записи электронной. . .	модель ЗдравоСохранения 5. Меньше увольнений- больше дохода! anaschu 24.03.2026 Теперь система здравосохранения уменьшает количество увольнений. 9TO2GP2bpX4 a42b81fb172ffc12ca589c7898261ccb/ https:/ / rutube. ru/ video/ a42b81fb172ffc12ca589c7898261ccb/ Слева синяя линия -. . .	Midnight Chicago Blues kumehtar 24.03.2026 Такой Midnight Chicago Blues, знаешь?. . Когда вечерние улицы становятся ночными, а ты не можешь уснуть. Ты идёшь в любимый старый бар, и бармен наливает тебе виски. Ты смотришь на пролетающие. . .

@alena05 0 / 0 / 0 Регистрация: 21.12.2012 Сообщений: 5

	Поиск в глубину 22.12.2012, 21:19. Показов 3821. Ответов 8 Метки нет (Все метки) Здравствуйте! Мне задали реализовать алгоритм ограниченного поиска в глубину без повторов и применить его для игры "8" (аналог пятнашек размерности 33 с числами от 1 до 8 и пустой клеткой). Насколько я поняла, необходимо воспользоваться уже описанным у Вас алгоритмом - Поиск в пространстве состояний (поиск по графам тоже сюда!), поиск с итерационным заглублением. Но как его модифицировать я не могу понять=(. Помогите пожалуйста, заранее спасибо. Добавлено через 21 час 35 минут* Насколько я понимаю, дожна быть функция move([X1,X2,X3,X4,X5,0,X6,X7,X8]) и перебрать перестановки для разных вариантов расположения пустой клетки, правильно? 0

@Грымзик 2507 / 1483 / 37 Регистрация: 14.09.2009 Сообщений: 2,740
	24.12.2012, 21:55
	Нет, не именно это. Подумайте сами, нарисуйте поле, и посмотрите в каких случаях недопустимо вверх передвинуть. 0

@alena05 0 / 0 / 0 Регистрация: 21.12.2012 Сообщений: 5
	08.01.2013, 08:58 [ТС]
	Все работает,спасибо огромное Добавлено через 5 часов 17 минут Только при нерешаемых комбинацияхпроисходит зацикливание 0

@Грымзик 2507 / 1483 / 37 Регистрация: 14.09.2009 Сообщений: 2,740
	08.01.2013, 14:13
	В Level>100 поменяйте 100 на число поменьше. 1