Каков может быть эффективный подход для решения 8 проблем загадки?

Question

Каков может быть эффективный подход для решения 8 проблем загадки?

Ни один из самых высоких проголосовавших ответов не корректен на 2000 SQLServer. Возможно, они использовали различную версию.

Вот правильные версии их обоих на 2000 SQLServer.

select t.range as [score range], count(*) as [number of occurences]
from (
  select case  
    when score between 0 and 9 then ' 0- 9'
    when score between 10 and 19 then '10-19'
    else '20-99' end as range
  from scores) t
group by t.range

или

select t.range as [score range], count(*) as [number of occurences]
from (
      select user_id,
         case when score >= 0 and score< 10 then '0-9'
         when score >= 10 and score< 20 then '10-19'
         else '20-99' end as range
     from scores) t
group by t.range

18

algorithm logic puzzle a-star 8-puzzle

задан Community 8 February 2017 в 14:15

4 ответа

Другие вопросы по тегам:

algorithm logic puzzle a-star 8-puzzle

Похожие вопросы:

score 11 · Answer 1

Вы можете использовать эвристику, основанную на позициях чисел, то есть чем выше общая сумма всех расстояний каждой буквы от ее целевого состояния, тем выше эвристическое значение . Затем вы можете реализовать поиск A *, который может оказаться оптимальным с точки зрения временной и пространственной сложности (при условии, что эвристика монотонна и допустима). http://en.wikipedia.org/wiki/A* _search_algorithm

score 4 · Answer 2

Пончик понял! IDDFS сделает свое дело, учитывая относительно ограниченное пространство поиска этой головоломки. Поэтому было бы эффективно ответить на вопрос ОП. Было бы найдено оптимальное решение, но не обязательно с оптимальной сложностью.

Реализация IDDFS была бы более сложной частью этой проблемы, Я просто хочу предложить простой подход к управлению доской, правилам игры и т. Д. Это, в частности, касается способа получения начальных состояний для решаемой головоломки. Намек в примечаниях к вопросу, что не все случайные наборы из 9 тайтов (учитывая, что пустой слот является особой плиткой), дадут решаемую головоломку. Это вопрос математической четности ... Итак, вот предложения по моделированию игры:

Составьте список всех матриц перестановок 3x3, которые представляют допустимые «ходы» игры. Такой список представляет собой подмножество 3x3s со всеми нулями и двумя единицами. Каждая матрица получает идентификатор, который будет довольно удобно отслеживать ходы в дереве поиска IDDFS. Альтернативой матрицам является наличие двух кортежей номеров позиций тайлов для обмена, это может привести к более быстрой реализации.

Такие матрицы можно использовать для создания начального состояния головоломки, начиная с состояния «выигрыш», и выполнение произвольного числа перестановок, выбранных случайным образом. Помимо обеспечения разрешимости начального состояния, этот подход также обеспечивает ориентировочное количество ходов, с помощью которых можно решить данную головоломку.

Теперь давайте просто реализуем алгоритм IDDFS и [шутка] вернем задание на пятерку [/ joke] ...

score 6 · Answer 3

Поскольку ОП не может опубликовать изображение, он говорит об этом:

8 Puzzle - Initial State

Что касается решения этой головоломки, обратите внимание на итеративное углубление в глубину алгоритм поиска , соответствующий задаче 8-головоломки на этой странице .

score 4 · Answer 4

Это пример классического алгоритма кратчайшего пути. Вы можете узнать больше о кратчайшем пути здесь и здесь .

Короче говоря, думайте обо всех возможных состояниях головоломки как о вершинах некоторого графа. С каждым ходом вы меняете состояния, поэтому каждое допустимое движение представляет собой край графа. Поскольку ходы не требуют затрат, вы можете думать, что стоимость каждого хода равна 1. Следующий псевдокод, подобный C ++, подойдет для этой задачи:

{
int[][] field = new int[3][3];
//  fill the input here
map<string, int> path;
queue<string> q;
put(field, 0); // we can get to the starting position in 0 turns
while (!q.empty()) {
    string v = q.poll();
    int[][] take = decode(v); 
    int time = path.get(v);
    if (isFinalPosition(take)) {
        return time;
    }
    for each valid move from take to int[][] newPosition {
        put(newPosition, time + 1);
    }
}
// no path
return -1;
}

void isFinalPosition(int[][] q) {
    return encode(q) == "123456780"; // 0 represents empty space
}
void put(int[][] position, int time) {
    string s = encode(newPosition);
    if (!path.contains(s)) {
        path.put(s, time);
    }
}

string encode(int[][] field) {
    string s = "";
    for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) s += field[i][j];
    return s;
}

int[][] decode(string s) {
    int[][] ans = new int[3][3];
    for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) field[i][j] = s[i * 3 + j];
    return ans;
}