• Кратчайший путь через несколько точек?

    @New-Developer Автор вопроса
    Решил задачу следующим образом: пусть n - количество соединяемых узлов, k - количество связей между узлами, или сегментов, k = n - 1. Например, есть 4 узла, которые надо соединить в порядке 1-2-3-4. Нужно сгенерировать k - 1 уровней сегментов, а на последнем, k уровне соединить оставшийся узел/сегмент с предыдущей комбинацией сегментов. Для всех уровней, кроме k, важен порядок соединения, так как например, A* с манхэттенской эвристикой находит разные маршруты для точек 1 и 2 в зависимости от порядка их соединения. Рассмотрим первый уровень сегментов для 4 узлов. На нем возможно 2 * k поисков A*, а именно: 1-2, 2-1, 2-3, 3-2, 3-4, 4-3. Теперь для каждого сегмента необходимо сгенерировать второй уровень сегментов. На примере 1-2 получаем варианты соединений с соседними узлами, либо генерируем варианты соединений остальных точек, а 1-2 отмечаем препятствием: 12-3, 3-21, 3-4, 4-3. Получили k - 1 уровней. Теперь на последнем, k уровне находим маршрут в любом направлении между 2 предыдущими уровнями или предыдущим уровнем и последним узлом, то есть: 123-4, 321-4, 34-12, 43-12. Теперь проделываем то же самое для остальных 5 сегментов первого уровня и находим кратчайший маршрут.
    Количество сгенерированных вариантов соединений всех узлов равно 2^(k - 1) * k! Для 3, 4, 5, 6 узлов это будет 4, 24, 192, 1920 вариантов соответственно. Количество запусков поиска пути будет равно сумме поисков на каждом уровне генерации сегментов, то есть 8, 54, 440, 4410 для 3, 4, 5, 6 узлов соответственно, найдено эмпирическим методом, общая формула похожа на сумму арифметико-геометрической прогрессии. Ниже приведен код на JS для подсчета вариантов соединений и поисков пути.
    let n = 5, k = n - 1, acc = k > 1 ? 2 * k : 0, out = acc || 1;
    for (let prev = acc - 2; prev > 2; prev -= 2) {
      acc *= prev;
      out += acc
    }
    console.log('Количество вариантов соединения =', acc || 1);
    console.log('Количество поисков A* =', out + acc);
    /*
    n = 3, k = 2: 8: 4 + 4;
    n = 4, k = 3: 54: 6 + 24 + 24;
    n = 5, k = 4: 440: 8 + 48 + 192 + 192;
    n = 6, k = 5: 4410: 10 + 80 + 480 + 1920 + 1920
    */
  • Кратчайший путь через несколько точек?

    @New-Developer Автор вопроса
    New Developer, предположение оказалось неправильным.
  • Кратчайший путь через несколько точек?

    @New-Developer Автор вопроса
    Ознакомлюсь с этими алгоритмами. Пока предположил, что можно ставить преграды на точках, которые не являются начальными или конечными. Эти "тупики" должны окружать узел так, что к нему можно попасть только с одной стороны. Потом вращать эти преграды, чтобы получить новые комбинации "стенок", одновременно с алгоритмами A* или Дейкстры. Оставшиеся начальный и конечный узел выбирать по приоритету: либо по наибольшему количеству свободных связей в соседней точке, либо по наименьшему расстоянию к соседу. Примерно максимальная сложность такого метода будет (n - 1)*4^(n - 2) поисков пути, где n - количество соединяемых узлов, но если не выбирать приоритет крайних точек, то в 2 раза больше.
  • Кратчайший путь через несколько точек?

    @New-Developer Автор вопроса
    Alexandroppolus, да, не решается, в том числе если все узлы у одного края, но расположены не по порядку или если расположены вплотную друг к другу и соседние по диагонали A(1,2) -> B(2,3) -> C(2,2) -> D(1,3)
  • Кратчайший путь через несколько точек?

    @New-Developer Автор вопроса
    Wataru, сетка без стенок/дырок, если не считать стенками ранее пройденные пути, насчет ребер - подобную задачу раньше не решал, но читал что в невзвешенном графе в начале расчетов для ребер нужно ставить длину 1.
  • Кратчайший путь через несколько точек?

    @New-Developer Автор вопроса
    Wataru, от 3 до 6. Например, 3 точки, все пронумерованы от 1 до 3, соответственно соединить 1 со 2, а 2 с 3.
  • Кратчайший путь через несколько точек?

    @New-Developer Автор вопроса
    Akina, сетка 10 на 10 клеток.
  • Где ошибка в алгоритме?

    @New-Developer Автор вопроса
    При построении алгоритма узлы из таблицы O я отметил черным, из Active - красным. Ошибка в том, что при поиске вниз могла произойти ситуация, когда черных узлов больше нет, можно добавить только красные, при length > 7.
    Исправил ситуацию:
    function countPatternsFrom2(firstPoint, length) {
      if (length > 9 || length == 0) return 0;
      if (length == 1) return 1;
      if (length == 2) return O[firstPoint].length;
      let sum = 0, stack = [firstPoint], actived = [], id = 0, d = true;
      while (stack.length) {
        if (id > -1) stack.push(O[stack.slice(-1)[0]][id]);
        let v0 = stack.slice(-1)[0], w = stack.slice(-2)[0], x = stack.length;
        if (x + 1 == length) {
          O[v0].forEach(v => { if (!stack.includes(v)) sum++ });
          for (let key in Active) {
            if (stack.includes(key) && v0 in Active[key] && !stack.includes(Active[key][v0])) {
              sum++
            }
          };
          d = false
        }
        if (d) {
          id = O[v0].findIndex(v => !stack.includes(v));
          if (id == -1) {
            let L = '';
            for (let key in Active) {
              if (stack.includes(key) && v0 in Active[key] && !stack.includes(Active[key][v0])) {
                L += Active[key][v0]
              }
            }
            if (L.length) {
              stack[x] = L[0];
              actived[x] = L.slice(1)
            }
          }
          continue
        };
        if (actived[x - 1] == `${actived[x - 1]}`) {
          if (actived[x - 1].length) {
            stack[x - 1] = actived[x - 1][0];
            actived[x - 1] = actived[x - 1].slice(1);
            d = true
          } else {
            stack.length--;
            actived.length = stack.length
          }
          continue
        }
        id = O[w].findIndex((v, i) => i > O[w].indexOf(v0) && !stack.includes(v));
        stack.pop();
        if (id == -1) {
          let L = '';
          for (let key in Active) {
            if (stack.includes(key) && w in Active[key] && !stack.includes(Active[key][w])) {
              L += Active[key][w]
            }
          }
          if (L.length) {
            stack[x - 1] = L[0];
            actived[x - 1] = L.slice(1);
            d = true
          }
        } else d = true
      }
      return sum
    }
    console.log(countPatternsFrom2('E', 9));

    Потом переделал на самый оптимальный вариант, который чуть медленнее BFS, но потребляет мало памяти:
    function countPatternsFrom2(firstPoint, length) {
      if (length > 9 || length < 1) return 0;
      let sum = 0, stack = [firstPoint], que = [''], down = true;
      while (stack.length) {
        let x = stack.length, v0 = stack[x - 1];
        if (x == length) {
          sum += que[x - 1].length + 1;
          down = false;
          stack.pop();
          que.pop();
          x--
        }
        if (down) {
          let L = '';
          O[v0].forEach(v => { if (!stack.includes(v)) L += v });
          for (let key in Active) {
            if (stack.includes(key) && v0 in Active[key] && !stack.includes(Active[key][v0])) {
              L += Active[key][v0]
            }
          }
          stack.push(L[0]);
          que.push(L.slice(1))
        } else {
          if (que[x - 1]) {
            stack[x - 1] = que[x - 1][0];
            que[x - 1] = que[x - 1].slice(1);
            down = true
          } else {
            stack.pop();
            que.pop()
          }
        }
      }
      return sum
    }
    console.log(countPatternsFrom2('E', 9))

    Здесь que - массив следующих узлов, но в отличии от actived туда добавляются и черные и красные, d или down - флаг для спуска вниз.
    С каким BFS сравнивал:
    function countPatternsFrom2(firstPoint, length) {
      if (length == 1) return 1;
      if (length > 9) return 0;
      let sum = 0, visited = [[firstPoint]], next = [];
      for (let counter = length; counter > 0; counter--) {
        visited.forEach(v => {
          let x = v.length + 1;
          O[v[0]].forEach(w => {
            if (!v.includes(w)) x == length ? sum++ : next.push([w].concat(v))
          });
          for (key in Active) {
            if (v.includes(key) && v[0] in Active[key]) {
              if (!v.includes(Active[key][v[0]])) x == length ? sum++ :
                next.push([Active[key][v[0]]].concat(v))
            }
          }
        });
        visited = next.slice();
        next = [];
      }
      return sum
    }
    console.log(countPatternsFrom2('E', 9))
  • Где ошибка в алгоритме?

    @New-Developer Автор вопроса
    Удалось добиться правильных вычислений при 7 соединяемых точках путем замены блока
    if (x == length) {
          id = O[w].findIndex((v, i) => i > O[w].indexOf(v0) && !stack.includes(v));
          stack.pop();
          sum++;
          if (id == -1) {
            for (key in Active) {
              if (stack.includes(key) && w in Active[key] && !stack.includes(Active[key][w])) {
                sum++
              }
            }
          }
          continue
        }

    на
    if (x + 1 == length) {
          O[v0].forEach(v => { if (!stack.includes(v)) sum++ });
          for (key in Active) {
            if (stack.includes(key) && v0 in Active[key] && !stack.includes(Active[key][v0])) {
              sum++
            }
          }
          id = -1
        }
  • Где ошибка в алгоритме?

    @New-Developer Автор вопроса
    Отследить ошибку при length больше 5 не представляю возможным, так как получается более 10000 итераций.
  • Как исправить функцию?

    @New-Developer Автор вопроса
    Fedor Vlasenko, довольно медленное, но работает.
  • Как исправить функцию?

    @New-Developer Автор вопроса
    С массивом [21, 1, 45, 54, 12, 11] получается 21145542111, или я что-то намудрил.
  • Как исправить функцию?

    @New-Developer Автор вопроса
    Alexandroppolus, исправил.
  • Как исправить функцию?

    @New-Developer Автор вопроса
    Alexandroppolus, тоже рассматривал такой вариант, но хотелось бы без генерации перестановок.
  • Как исправить функцию?

    @New-Developer Автор вопроса
    Fedor Vlasenko, есть только ссылка на похожую задачу https://www.codewars.com/kata/55983863da40caa2c900..., но она довольно простая, потому что в процессе вычислений там получается массив с элементами из 1 цифры, которые сравнивать легко. Я поставил здесь ограничение на максимальную цифру 99, чтобы можно было решить через кучу условий сравнения первой и второй цифр соседних элементов массива для нахождения первого и второго индекса в программе из вопроса. В массиве не более 10 элементов.
  • Как исправить функцию?

    @New-Developer Автор вопроса
    WbICHA, например, есть массив [9, 1, 3, 60, 1, 72, 9, 2], при объединении его элементов получится число 9136017292, нужно переставить элементы массива так, чтобы при их объединении получилось следующее большее число, то есть 9136019272. При этом цифры в двузначных элементах массива менять местами нельзя.
  • Двумерный массив одним циклом?

    @New-Developer Автор вопроса
    А с заполнением минимум вложенный цикл ?
  • Можно ли разделить строку с сохранением разделителей без регулярного выражения?

    @New-Developer Автор вопроса
    Stalker_RED, следуя инструкциям, дописал регулярку
    console.log('5 /(2-  3)* 1.333333 + -11 '.match(/\+|\(|\)|\-|\*|\/|[\d.]+/g))
  • Можно ли разделить строку с сохранением разделителей без регулярного выражения?

    @New-Developer Автор вопроса
    Aleksandr-JS-Developer, как удалить пробелы, находил в интернете .replace(/\s/g,''), а отделить десятичное число не пойму как:
    let st='5 /(2-  3)* 1.333333 + -11 ';
    console.log(st.replace(/\s/g,'').match(/\d+|\+|\(|\)|\-|\*|\/|[\d.]/g))