• Поиск по форумам
  •  
      Этот форум закрыт. Новый форум располагается по адресу http://forum.use.ru  

      Nordnet Форум
      Программирование
      Алгоритм игры "15"
     
    Страницы: 1
    Автор Тема:  Алгоритм игры "15"
    torchok 

    регистрация: 04-07-2006 в 10:53
    сообщений: 16

    отправлено 04-07-2006 11:39    
    Наверное, все знают такую игру. Короче, есть матрица 4х4, в ней числа 0..15.
    Задача: упорядочить числа за _наименьшее_ число ходов.
    Кто небудь знает алгоритм ?
    Force 

    регистрация: 06-12-2001 в 00:09
    сообщений: 20128

    отправлено 04-07-2006 21:48    
    2 torchok:
    Если числа от 0 до 15, то скорее всего тебе подойдет что-нить типа quicksort.
    А если от 1 до 15, да еще с дыркой, где-нить, то тут надо думать, так я не знаю (да еще и не забыть, что иногда в принципе нельзя решить эту задачу).
    torchok 

    регистрация: 04-07-2006 в 10:53
    сообщений: 16

    отправлено 05-07-2006 19:45    
    Имеются ввиду числа от 1 до 15, а 0 символизирует дырку :-)
    Ход - это обмен значений пустой ячейки(в которой 0) с одной из 4-х соседних
    Force 

    регистрация: 06-12-2001 в 00:09
    сообщений: 20128

    отправлено 05-07-2006 21:35    
    2 torchok:
    Тебе нужен алгоритм, который находит самую быструю перестановку, или алгоритм, который достаточно быстро решает любую комбинацию?
    torchok 

    регистрация: 04-07-2006 в 10:53
    сообщений: 16

    отправлено 05-07-2006 22:37    
    2 Force:

    Нужен алгоритм, который будет собирать эту фигню за наименьшее кол-во ходов и распечатывать их
    Тут, похоже, без рекурсии необойтись...
    torchok 

    регистрация: 04-07-2006 в 10:53
    сообщений: 16

    отправлено 05-07-2006 22:47    
    нашёл я тут один алгоритм, какой-то euristic-serach, но
    он находит не кратчайшее решение, а одно из возможных, негодицца.
    Force 

    регистрация: 06-12-2001 в 00:09
    сообщений: 20128

    отправлено 06-07-2006 10:41    
    2 torchok:
    Я тут подумал, по идее кратчайшее решение можно найти только полным перебором (возможно можно отсекать совершенно левые пути), ибо задача сама по себе не очень алгоритмичная. Можно придумать комбинации, для которых существует единственный оптимальный алгоритм, но этот алгоритм совершенно не пригоден для другой раскладки.
    А полный перебор для пятнашек весьма тяжелая задача. Где-то 16! вариантов, так что придется довольствоваться тем, что имеешь.

    ЗЫ: Задача заинтересовала, еще подумаю о ней.
    Boreas 

    регистрация: 08-03-2003 в 00:54
    сообщений: 19

    отправлено 09-07-2006 00:37    
    Есть хорошая небольшая статья про эту задачу в Википедии (http://en.wikipedia.org/wiki/N-puzzle). Лучше перебора с эвристиками ничего не придумано. Обобщенная задача NP-трудна.
    ALIEN Xupypr 

    регистрация: 31-10-2004 в 15:53
    сообщений: 248

    отправлено 12-07-2006 22:38    
    unit Unit1;

    interface

    uses
    Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
    Dialogs;

    type
    TForm1 = class(TForm)
    procedure FormCreate(Sender: TObject);
    procedure FormPaint(Sender: TObject);
    procedure ShowPole;
    procedure Mixer;
    procedure FormMouseDown(Sender: TObject; Button: TMouseButton;
    Shift: TShiftState; X, Y: Integer);
    private
    { Private declarations }
    public
    { Public declarations }
    end;

    const H=4; W=4;// размер поля - 4х4
    CH=64; CW=64;// размер клеток - 16х16

    var
    // правильное расположение фишек
    stp:array[1..H,1..W] of Byte=(( 1, 2, 3, 4),( 5, 6, 7, 8),( 9,10,11,12),(13,14,15, 0));// игровое поле
    pole:array[1..H,1..W] of Byte;
    ex,ey:integer;// координаты пустой клетки

    Form1: TForm1;

    implementation

    {$R *.dfm}

    procedure NewGame;
    var i,j:integer;
    begin
    // исходное (правильное) положение
    for i:=0 to H+1 do
    for j:=0 to W+1 do
    pole[i,j] := stp[i,j];
    Form1.Mixer;// перемешать фишки
    Form1.ShowPole;// отобразить поле
    end;

    function Finish: boolean;
    var row,col:integer;
    i:integer;
    begin
    row:=1; col:=1;
    Finish := True; // пусть фишки в нужном порядке
    for i:=1 to 15 do
    begin
    if pole[row,col] i then
    begin
    Finish:= False;
    break;
    end;
    // к следующей клетке
    if col=1) and (x2=1) and (y2
    2HD 

    регистрация: 18-07-2004 в 20:32
    сообщений: 1045

    отправлено 18-01-2007 13:18    
    Игра в 15 решается (как уже сказали, но перефразирую) деревьями решений(как и многие задачи такого рода, типа крестиков-ноликов, шашек, шахмат и т.д. т т.п.).

    Обратится можно к старенькой такой книжке \"Искусственный интеллект\". Автор: Нильсон. Там очень хорошо всё написано по этому поводу(в основном на идейном уровне).
    Страницы: 1