Премини към съдържанието
JoeBlack

Проблем с backtracking алгоритъм

Препоръчан отговор


Здравейте,

Направих програма, която при въведено име от клавиатурата проверява дали и колко пъти се повтаря в дадена матрица. Не разбирам защо след въвеждане на името програмата спира.

private static char[][] words= { { 'k', 'o', 'k', 'o' }, { 'e', 'v', 'n', 'h', }, { 'i', 'n', 'a', 'v', },
       { 'm', 'v', 'v', 'n', }, { 'q', 'r', 'i', 't', } };

private static void findName(int row, int col, String direction) {

   Scanner input = new Scanner(System.in);
   System.out.println("Enter name.");

   String name = input.nextLine();

   StringBuilder word = new StringBuilder();
   int counter = 0;

   if ((col < 0) || (row < 0) || (col >= words[0].length) || (row >= words.length)) {
       return;
   }

   if (words[row][col] != ' ') {
       return;
   } else {
       word = word.append(lab[row][col]);
   }

   if (word.equals(name)) {
       counter++;
       System.out.printf("Name - {%s} found %s times%n", name, counter);
       word = null;
   }

   words[row][col] = 's';
   findName(row, col - 1, "L");
   System.out.printf("L");
   findName(row - 1, col, "U");
   System.out.printf("U");
   findName(row, col + 1, "R");
   System.out.printf("R");
   findName(row + 1, col, "D");
   System.out.printf("D");
   words[row][col] = ' ';
}

public static void main(String[] args) {
   findName(0, 0, "R");
}

 

Редактирано от JoeBlack (преглед на промените)

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

Промених си кода така, но пак не става.

   if (words[row][col] != ' ') {
       return;

	private static char[][] words = { { 'k', 'o', 'k', 'o' }, { 'e', 'v', 'n', 'h', }, { 'i', 'n', 'a', 'v', },
			{ 'm', 'v', 'v', 'n', }, { 'q', 'r', 'i', 't', } };

	private static void findName(int row, int col, String direction) {

		Scanner input = new Scanner(System.in);
		System.out.println("Enter name.");

		String name = input.nextLine();
		

		StringBuilder word = new StringBuilder();
		int counter = 0;

		if ((col < 0) || (row < 0) || (col >= words[0].length) || (row >= words.length)) {
			return;
		}


		if (word.equals(name)) {
			counter++;
			System.out.printf("Name - {%s} found %s times%n", name, counter);
			word = null;
			return;
		} else {
			word = word.append(words[row][col]);
		}

		
		words[row][col] = 's';
		findName(row, col - 1, "L"); 
		System.out.printf("L");
		findName(row - 1, col, "U"); 
		System.out.printf("U");
		findName(row, col + 1, "R"); 
		System.out.printf("R");
		findName(row + 1, col, "D"); 
		System.out.printf("D");
		words[row][col] = ' ';
	}

	public static void main(String[] args) {
		findName(0, 0, "R");
	}

 

Редактирано от JoeBlack (преглед на промените)

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

Здравейте !

Имам особеното чувство, че това не е пълния код на програмата.

Например не виждам дефиниция и инициализация на променливата 

lab

@Ken Ви даде една много добра насока и защо изпълнението на рекурсията прекъсва още на първото си рекурсивно извикване - сменете знака от != на ==

Поздрави !

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

Обикновено средите за програмиране предлагат възможност за изпълнение на кода ред по ред и наблюдение на междинните резултати, точно с цел откриване на грешки.


Сподели този отговор


Линк към този отговор
Сподели в други сайтове

Здравейте !

Имам особеното чувство, че това не е пълния код на програмата.

Например не виждам дефиниция и инициализация на променливата 

lab

@Ken Ви даде една много добра насока и защо изпълнението на рекурсията прекъсва още на първото си рекурсивно извикване - сменете знака от != на ==

Поздрави !

Копирал съм пълния код на програмата. Сега дебъгнах и видях, че има проблем със Scanner-а. За сега хардкоднах едно име, но и така не става.

 

private static char[][] words = { { 'i', 'v', 'a', 'n' },
									  { 'e', 'v', 'n', 'h', },
									  { 'i', 'n', 'a', 'v', },
									  { 'm', 'v', 'v', 'n', },
									  { 'q', 'r', 'i', 't', }
									 };

	private static void findName(int row, int col, String direction) {

		String name = "ivan";

		StringBuilder word = new StringBuilder();
		int counter = 0;

		if ((col < 0) || (row < 0) || (col >= words[0].length) || (row >= words.length)) {
			return;
		}

		if (words[row][col] == ' ') {
			return;
		} else {
			word = word.append(words[row][col]);
		}

		if (word.equals(name)) {
			counter++;
			System.out.printf("Name - {%s} found %s times%n", name, counter);
			word = null;
		}

		words[row][col] = 's';
		findName(row, col - 1, "L");
		System.out.printf("L");
		findName(row - 1, col, "U");
		System.out.printf("U");
		findName(row, col + 1, "R");
		System.out.printf("R");
		findName(row + 1, col, "D");
		System.out.printf("D");
		words[row][col] = ' ';
	}

	public static void main(String[] args) {
		findName(0, 0, "R");
	}

 

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

Здравейте !

Довечера ще погледна малко по-детайлно нещата, но като за начало обърнете внимание на следното:

1) Backtracking алгоритмите имат доста специфичен начин на запис, едно от които е revert-ване на данните до предходен state. Което автоматично означава, че промяна по самата матрица НЕ трябва да има. Допълнително, означава, че този StringBuilder, който се прави е доста безсмислен, защото той се създава на всяко рекурсивно извикване - т.е. всяко извикване ще направи нов обект и това "присвояване", което се прави е напълно ненужно.

2) Следенето на обходени елементи е направено с промяна на данните, което от 1) казахме, че не трябва да се прави. Това предразполага за поддържане на нова структура, която да track-ва кои елементи вече са използвани. В текущата имплементация няма два важни елемента - reject, който веднага да каже, че няма възможно продължение, което да доведе до валиден резултат и stepBack, който да върне данните в предходно състояние. 

3) Следния ред не прави това, което си мислите:

if (word.equals(name)) {

За разлика от String.equals(), StringBuilder.equals(Object other) проверява за еднаквост по референция (this == other) а не по текуща стойност на данните в буфера си. Логично, познайте кога това нещо ще даде true.

За да използвате equals по този начин, извлечете String обект от StringBuilder-а чрез toString() метода му и тогава equals()-а ще проработи.

Поздрави !

  • Харесва ми 2

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

<spoilerAlert>Тази тема е от BgDev.</spoilerAlert>

Или тамошната е от тук - зависи къде първо е писано ...

Няма да е за първи, а със сигурност няма да е и за последен път тоя номер.

Свиква се :)

  • Харесва ми 1

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

Виж този код, условието е да проверява символ по символ от зададена дума и да изкарва позицията на буквата, от предварително зададената матрица. Не е точно това което търсиш, но ще ти е от помощ.

Успех!

import java.util.Scanner;
import java.lang.String;
import java.util.Arrays;
public class HelloJava {

    public static void main(String[] args){
        String [] azbuka = {"a","q","w","e","r","t","y","u","i","o","p","s","d","f","g","h","j","k","l","z","x","c","v","b","n","m",};
        System.out.println(Arrays.deepToString(azbuka));
        Scanner input = new Scanner(System.in);
        String word=input.nextLine(); //asen
        String[] parts = word.split(" ".trim());
        System.out.print(Arrays.deepToString(parts));
        for (int i=0;i<word.length();i++){
            for (int index=0;index<azbuka.length;index++){
                if (azbuka[index].equals(parts)){
                    System.out.printf("%nStoinosta e %d",(index+1));
                }
            }
            }
    }
        }
        
        

 

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

Регистрирайте се или влезете в профила си за да коментирате

Трябва да имате регистрация за да може да коментирате това

Регистрирайте се

Създайте нова регистрация в нашия форум. Лесно е!

Нова регистрация

Вход

Имате регистрация? Влезте от тук.

Вход

×

Информация

Поставихме бисквитки на устройството ви за най-добро потребителско изживяване. Можете да промените настройките си за бисквитки, или в противен случай приемаме, че сте съгласни с нашите условия за ползване.