|
|
[ olp29 @ 18.09.2014. 18:07 ] @
|
| Zdravo svima.
Radim jedan zadatak i naisao sam na ozbiljan problem. Nadam se da svi razumete engleski ali ako je potrebno mogu i da ga prevedem. Naime zadatak glasi ovako:
We have two strings A and B with the same super set of characters. We need to change these strings to obtain two equal strings. In each move we can perform one of the following operations:
1- swap two consecutive characters of a string
2- swap the first and the last characters of a string
A move can be performed on either string.
What is the minimum number of moves that we need in order to obtain two equal strings?
Input Format and Constraints:
The first and the second line of the input contains two strings A and B. It is guaranteed that the superset their characters are equal.
1 <= length(A) = length(B) <= 2000
All the input characters are between 'a' and 'z'
Output Format:
Print the minimum number of moves to the only line of the output
Sample input:
aab
baa
Sample output:
1
Explanation:
Swap the first and last character of the string aab to convert it to baa. The two strings are now equal.
Ono sto sam ja razmisljao jeste da se verovatno radi o dinamickom programiranju i sve ideje koje sam do sada imao nisu ni vredne pomena. Takodje, ja radim na nekoj ideji i resavanju tako da ako se desi da pre odgovora odradim ovaj zadatak, postavicu ga da bi i ostali znali.
P.S. Svaka sugestija, ideja je dobrodosla. Ne mora da bude resenje.
Hvala. |
[ olp29 @ 21.09.2014. 16:24 ] @
Ovo je neka moja najbolja ideja do sada, ali ipak ne vraca minimum pomeranja... Evo koda ako ista znaci:
Code:
package com.taskMinimumStringMoves;
import java.util.Scanner;
public class MinimumStringMoves {
public static void swap(char aChar, char bChar) {
char cChar;
cChar = aChar;
aChar = bChar;
bChar = cChar;
}
public static void main(String[] args) {
int moves = 0;
Scanner scanner = new Scanner(System.in);
System.out.println("Enter the string A:");
while (!scanner.hasNext("[A-Za-z]+")) {
System.out
.println("Nope, that's not it! Enter the value from \"a\" to \"z\"."
+ "Enter your string A again!");
scanner.nextLine();
}
String a = scanner.nextLine();
a.toLowerCase();
System.out.println("Enter the string B:");
while (!scanner.hasNext("[A-Za-z]+")) {
System.out
.println("Nope, that's not it! Enter the value from \"a\" to \"z\"."
+ "Enter your string B again!");
scanner.nextLine();
}
String b = scanner.nextLine();
b.toLowerCase();
scanner.close();
char[] aChar = a.toCharArray();
char[] bChar = b.toCharArray();
if ((a.length() >= 1 && a.length() <= 2000) && a.length() == b.length()) {
if (aChar[0] != bChar[0]) {
if (aChar[0] == bChar[bChar.length - 1]) {
swap(bChar[0], bChar[bChar.length - 1]);
moves++;
} else if (bChar[0] == aChar[aChar.length - 1]) {
swap(aChar[0], aChar[bChar.length - 1]);
moves++;
}
}
for (int i = 0; i < aChar.length; i++) {
if (aChar[i] == bChar[i]) {
continue;
}
for (int j = i + 1; j < aChar.length; j++) {
if (aChar[i] == bChar[j]) {
for (int k = j; k > i; k--) {
swap(bChar[k], bChar[k - 1]);
moves++;
}
break;
} else if (bChar[i] == aChar[j]) {
for (int k = j; k > i; k--) {
swap(aChar[k], aChar[k - 1]);
moves++;
}
break;
}
}
if (aChar == bChar) {
break;
}
}
System.out.println("Minimum moves: " + moves);
}
}
}
[ blekmor @ 24.09.2014. 03:04 ] @
Pročitao sam pitanje i odmah su mi pale na pamet dvije stvari. Možda ti pomognu, a možda ne. Simpatičan je problem, tako da ću vjerovatno ovih dana ozbiljnije razmisliti o njemu pa ću se javiti.
1. Predstavi stringove kao permutacije karaktera. Sjećam se da sam na fakultetu izučavao neki poznati algoritam za generisanje permutacija, koji je radio baš po principu zamjene mjesta. Nekako numerišeš permutacije, pa vidiš šta možeš da uradiš.
2. Pogledaj algoritam A*. Nekada davno sam preko njega rješavao problem pronalaska minimalnog broja koraka za rješavanje 8 puzzle problema, koji je nekako srodan problemu koji si ti izložio.
[ olp29 @ 24.09.2014. 12:47 ] @
Uradio sam nesto ovako, medjutim i dalje nije jos to to. Mislim da moram da uracunam da vidi da li je to 1 pomeranje,2 ili 3, itd.
Code:
char[] aChar = a.toCharArray();
char[] bChar = b.toCharArray();
char cChar;
if ((a.length() >= 1 && a.length() <= 2000) && a.length() == b.length()) {
if (aChar != bChar) {
for (int i = 0; i < aChar.length; i++) {
for (int j = i + 1; j < aChar.length; j++) {
if (aChar[i] != bChar[i]) {
if (aChar[j] == bChar[i] && j < aChar.length) {
cChar = aChar[j];
aChar[j] = aChar[i];
aChar[i] = cChar;
moves++;
} else if (aChar[aChar.length - 1] == bChar[i]) {
cChar = aChar[aChar.length - 1];
aChar[aChar.length - 1] = aChar[i];
aChar[i] = cChar;
moves++;
} else {
if (aChar[j] != aChar[i] && j < aChar.length) {
if (aChar[j] == bChar[j]) {
cChar = bChar[j];
bChar[j] = bChar[i];
bChar[i] = cChar;
moves++;
}
cChar = aChar[j];
aChar[j] = aChar[i];
aChar[i] = cChar;
moves++;
} else if (bChar[j] != bChar[i]
&& i + 1 < aChar.length) {
if (aChar[j] == bChar[j]
&& aChar[j] != aChar[i]) {
cChar = aChar[j];
aChar[j] = aChar[i];
aChar[i] = cChar;
moves++;
}
cChar = bChar[j];
bChar[j] = bChar[i];
bChar[i] = cChar;
moves++;
}
}
if (aChar == bChar) {
break;
}
}
}
}
}
System.out.println("Minimum number of moves: " + moves);
} [ river @ 24.09.2014. 13:13 ] @
Pozdrav,
Ukoliko se ne varam - postavka problema upucuje na jedan poznat algoritam: https://en.wikipedia.org/wiki/Levenshtein_distance . [ river @ 24.09.2014. 13:17 ] @
Ispravka, samo je na prvi pogled izgledalo kao Levenstajnova distanca, ali mozda ti slican algoritam da ideju kako da nastavis.
Pozdrav
[ blekmor @ 25.09.2014. 14:10 ] @
Neću ti pisati implementaciju algoritma, ali ću ti opisati algoritam koji rješava ovaj problem.
Naime problem možeš riješiti algoritmom A*. A* je verzija Dijestrinog algoritma za pronalazak najkraćeg puta izmedju dva čvora u grafu. Ti graf nećeš eksplicitno praviti, ali možeš posmatrati problem kao grafovski. Naime treba da dodješ od početnog čvora (prva riječ) do krajnjeg čvora (druga riječ). Iz svakog čvora možeš doći u nekog njegovog sina, kojih ima n, gdje je n veličina riječi. Sinove nekog čvora formiraš tako što zamjeniš dva susjedna slova. Tako npr. od čvora 1234, dobijaš sinove 2134,1324,1243 i 4231, jer osim susjednih slova, možeš mjenjati i prvo i poslednje, ako sam ja dobro razumio zadatak. Svakom generisanom sinu x dodjeljuješ neku vrijednost, f(x) = g(x) + h(x), gdje je g(x) cijena puta od polaznog čvora do čvora x (broj koraka/zamjena da se dodje od početnog čvora do čvora x), a h(x) je heuristička funkcija. Poenta ovog algoritma je u h(x). Heuristika je neka procjena. Naime, trebaš svakom čvoru da dodjeliš vrijednost "koliko je on udaljen od rešenja". Tako npr heuristika može da bude koliko slova nije na svom mjestu: Ako imamo čvor x=1243, a ciljani čvor je 1234, tada je h(x)=2 jer dva elementa: 3 i 4, nisu na svom mjestu. Naravno, heuristike mogu biti dobre i loše, to je na tebi da smisliš. Sada smo izračunali f(x) za svako dijete od trenutno posmatranog čvora. U sledećem koraku biramo ono dijete kome je f(x) najmanje. U jednom trenutku ćeš doći do ciljanog čvora, što je logično, jer ćeš da izlistaš sve permutacije. Ako je heuristička funkcija "admisible" (ne precjenjuje optimalno rešenje), onda ti ovaj algoritam nalazi najkraći put od početnog do krajnjeg čvora, odnosno najmanji broj koraka da transformišeš prvu riječ u drugu. Što je heuristika bolja, to algoritam radi brže. Kada je heuristička funkcija "admisible" i kada je "bolja" možeš pročitatu u priloženim linkovima.
http://en.wikipedia.org/wiki/A*_search_algorithm
http://en.wikipedia.org/wiki/Heuristic_function
http://feynmanliang.com/comparing-astar-heuristics/
Javi se ako ti nešto nije jasno ili ako ti bude potrebna dodatna pomoć. Mogu ti ovo implementirati u Javi, ali mislim da je poenta u tome da to uradiš sam. [ galaksija @ 25.09.2014. 14:18 ] @
Pa napiši čoveku algoritam !
Evo baš bih voleo da vidim @blekmor implementaciju (nije bitan jezik).
[ blekmor @ 25.09.2014. 14:51 ] @
Algoritam je opisan u detalje u mom prethodnom postu. To što ga ti ne znaš protumačiti je tvoj problem. Pored toga su ostavljeni linkovi za dodatne informacije. Implementacija nije napisana, jer je korisnik koji je postavio pitanje student (piše u opisu) i tražio je ideju ili sugestiju. U svojoj prvoj poruci sam mu dao sugestiju da koristi A*, ali ga izgleda nisam dovoljno zainteresovao, pa sam odlučio da mu detaljnije objasnim kako se problem može rješiti korištenjem A* algoritma. Moja namjera je da pomognem momku, a mislim da je ova vrsta pomoći bolja, nego da mu tutnem kod koji vjerovatno neće ni razumiti iz prve. Meni je puno lakše da napišem rješenje u 10ak linija koda nego da objašnjavam suštinu, kao što pokušavam. Ako bude htio da mu napišem implementaciju, biću rad da to uradim.
[ olp29 @ 25.09.2014. 20:33 ] @
@blekmor Hvala na pomoci i ideji. Ali imam jedno pitanje. Sve kako si objasnio mi je savrseno jasno, ali ja nemam zapravo cilj. Ako imam string perapare i parepera, jedini cilj koji imam je da oni budu jednaki. A da li ce biti na kraju parepare ili perapera ili pak praeprae totalno je nebitno. Samo je bitan broj minimalnih pomeranja.
Da li je onda bez obzira na ovu gore pomenutu cinjenicu primenjiv ovaj algoritam? Inace, totalno je u redu da mi ne das implementaciju. Ovo mi treba da uradim i shvatim. Ideje sam vec pokupio, gomila i probacu nesto. U slucaju da bas ne budem mogao da resim potrazicu kod. U svakom slucaju hvala!
Pozdrav!
[ galaksija @ 25.09.2014. 20:40 ] @
u prevodu, napiši čoveku algoritam, naravno, ako znaš.
[ blekmor @ 25.09.2014. 22:32 ] @
Ako transformišeš prvi string i dobiješ neki "medju-string", a paraleno transformišeš drugi string, i dobiješ taj isti "medju-string", biće ti potreban isti broj koraka kao kad transformišeš prvi string do tog "medju-stringa", i onda "medju-string" transformišeš do drugog stringa. To važi zato što je minimalan broj koraka da string A transformisao u string B jednak minimalnom broju koraka potrebnih za transformaciju stringa B u string A. Naravno, redoslijed koraka je obrnut, ali tebe to ne zanima, tebe zanima samo broj koraka. Znači da je algoritam primenljiv.
Javi kako napreduješ i ako ti bude trebala dodatna pomoć.
@galaksija
Algoritam sam mu napisao i objasnio. Sad da li ti mene troluješ, ili jednostavno ne znaš razliku izmedju algoritma i implementacije algoritma, to ne mogu da procjenim. Nadam se da je u pitanju ovo prvo. U tom slučaju sam se primio, i čestitam ti.(smajli) Pored toga sam već objasnio zašto nisam ovde napisao implementaciju algoritma koji rješava postavljeni problem, i o tome više neću pisati. Naravno, tebi mogu poslati implementaciju u privatnoj poruci, ukoliko to želiš, ali tu nema ništa zanimljivo; algoritam je jasan i implementacija je straightforward.
[ olp29 @ 13.10.2014. 09:08 ] @
Pozdrav svima. Izvinite zbog zakasnelog odgovora, ali evo da vam izbacim moje resenje:
Code:
public int findMinimumStringMovement() {
int moves = 0;
char[] aChar = a.toCharArray();
char[] bChar = b.toCharArray();
char cChar;
if (aChar != bChar) {
for (int i = 0; i < aChar.length; i++) {
for (int j = i + 1; j < aChar.length; j++) {
if (aChar[i] != bChar[i]) {
/*
* It checks if some character from the array of aChar
* is same as other character from the array of B and if
* it's j less then the length of the array. If it's
* true, then swap the characters and count moves
*/
if (aChar[j] == bChar[i] && j < aChar.length) {
for (int k = j; k > i; k--) {
cChar = aChar[k];
aChar[k] = aChar[k - 1];
aChar[k - 1] = cChar;
moves++;
}
/*
* In other case, if the last character of array
* aChar same as the some character of bChar and
* vice versa, then we should check if the i is
* equal to 0, in that case we swap 1st and last
* character of array and count as 1 move else if i
* value is less then the value of length of array
* divided with 2 then it swaps that character to
* the first one and then swaps with last and counts
* the moves.
*/
} else if (aChar[aChar.length - 1] == bChar[i]) {
if (i == 0) {
cChar = aChar[aChar.length - 1];
aChar[aChar.length - 1] = aChar[i];
aChar[i] = cChar;
moves++;
} else if (i < (aChar.length - 1) / 2) {
for (int k = i; k > 0; k--) {
cChar = aChar[k];
aChar[k] = aChar[k - 1];
aChar[k - 1] = cChar;
moves++;
}
cChar = aChar[i];
aChar[i] = aChar[aChar.length - 1];
aChar[aChar.length - 1] = cChar;
}
} else if (bChar[bChar.length - 1] == aChar[i]) {
if (i == 0) {
cChar = bChar[bChar.length - 1];
bChar[bChar.length - 1] = bChar[i];
bChar[i] = cChar;
moves++;
} else if (i < (aChar.length - 1) / 2) {
for (int k = i; k > 0; k--) {
cChar = aChar[k];
aChar[k] = aChar[k - 1];
aChar[k - 1] = cChar;
moves++;
}
cChar = aChar[i];
aChar[i] = aChar[aChar.length - 1];
aChar[aChar.length - 1] = cChar;
}
/*
* And the last case is if there is no other option,
* then we asks if some characters in array with
* positions i and j are different and if the j
* value is less then length of the array and do the
* swap.
*/
} else {
if (aChar[j] != aChar[i] && j < aChar.length) {
if (aChar[j] == bChar[j]) {
cChar = bChar[j];
bChar[j] = bChar[i];
bChar[i] = cChar;
moves++;
}
cChar = aChar[j];
aChar[j] = aChar[i];
aChar[i] = cChar;
moves++;
} else if (bChar[j] != bChar[i] && j < aChar.length) {
if (aChar[j] == bChar[j]
&& aChar[j] != aChar[i]) {
cChar = aChar[j];
aChar[j] = aChar[i];
aChar[i] = cChar;
moves++;
}
cChar = bChar[j];
bChar[j] = bChar[i];
bChar[i] = cChar;
moves++;
}
}
/*
* At the end, if arrays are equal, then it is done.
*/
if (aChar == bChar) {
break;
}
}
}
}
}
return moves;
}
Nadam se da vam je pomoglo.
Pozdrav. [ djoka_l @ 13.10.2014. 11:31 ] @
Pa, nije nam pomoglo iz više razloga. Možda je najvažniji taj što nismo ni imali problem, a ne manje važno je i to što tvoj program ne radi dobro.
Ajde, pusti kroz tvoj program da se nađe rešenje za stringove:
abcdefghijklmnopqrstuvwxyz
bzcdefghijklmnopqrstuvwxay
Rešenje je 3:
1. zameni mesta bz, dobije se zbcdefghijklmnopqrstuvwxay
2. zameni mesta ay, dobije se zbcdefghijklmnopqrstuvwxya
3. zameni mesta z i a, dobije se abcdefghijklmnopqrstuvwxyz, što je i trebalo da se dobije.
blekmor te je lepo uputio na rešenje, a ti nisi ni blizu...
[ djoka_l @ 13.10.2014. 11:45 ] @
Uzgred, evo jednog algoritma koji radi slično kao ovo što si ti napisao, ali ne daje optimalan broj pomeranja:
Uradi bubble sort nad prvim stringom i zapamti broj zamena z1.
Uradi bubble sort nad drugim stringom i zapamti broj zamena z2.
Ako su sada stringovi isti, onda je ukupan broj zamena Z=z1+z2.
Naravno, ovo nije optimalno, ali ti daje neku procenu:
1. kaže ti koja je GORNJA granica broja zamena (tj. dubinu pretrage posle koje treba da obustaviš pretraživanje)
2. kaže ti da li je uopšte MOGUĆE da od stringa2 napraviš string1. [ olp29 @ 13.10.2014. 12:39 ] @
@djoka_I interesantna stvar je ta sto meni vraca 3 promene... Nakon blizeg pogleda video sam da sam lose prekopirao kod. Imao sam duplikat istog, ali sam dao pogresan. Ovo je pravi, i uradjen je na istu foru i vraca dobar broj pomeranja. Evo koda:
Code:
public int findMinimumStringMovement() {
int moves = 0;
char[] aChar = a.toCharArray();
char[] bChar = b.toCharArray();
char cChar;
if (aChar != bChar) {
for (int i = 0; i < aChar.length; i++) {
for (int j = i + 1; j < aChar.length; j++) {
if (aChar[i] != bChar[i]) {
/*
* It checks if some character from the array of aChar
* is same as other character from the array of B and if
* it's j less then the length of the array. If it's
* true, then swap the characters and count moves
*/
if (aChar[j] == bChar[i] && j < aChar.length) {
for (int k = j; k > i; k--) {
cChar = aChar[k];
aChar[k] = aChar[k - 1];
aChar[k - 1] = cChar;
moves++;
}
/*
* In other case, if the last character of array
* aChar same as the some character of bChar and
* vice versa, then we should check if the i is
* equal to 0, in that case we swap 1st and last
* character of array and count as 1 move else if i
* value is less then the value of length of array
* divided with 2 then it swaps that character to
* the first one and then swaps with last and counts
* the moves.
*/
} else if (aChar[aChar.length - 1] == bChar[i]) {
if (i == 0) {
cChar = aChar[aChar.length - 1];
aChar[aChar.length - 1] = aChar[i];
aChar[i] = cChar;
moves++;
} else if (i < (aChar.length - 1) / 2) {
for (int k = i; k > 0; k--) {
cChar = aChar[k];
aChar[k] = aChar[k - 1];
aChar[k - 1] = cChar;
moves++;
}
cChar = aChar[i];
aChar[i] = aChar[aChar.length - 1];
aChar[aChar.length - 1] = cChar;
}
} else if (bChar[bChar.length - 1] == aChar[i]) {
if (i == 0) {
cChar = bChar[bChar.length - 1];
bChar[bChar.length - 1] = bChar[i];
bChar[i] = cChar;
moves++;
} else if (i < (aChar.length - 1) / 2) {
for (int k = i; k > 0; k--) {
cChar = aChar[k];
aChar[k] = aChar[k - 1];
aChar[k - 1] = cChar;
moves++;
}
cChar = aChar[i];
aChar[i] = aChar[aChar.length - 1];
aChar[aChar.length - 1] = cChar;
moves++;
}
/*
* And the last case is if there is no other option,
* then we asks if some characters in array with
* positions i and j are different and if the j
* value is less then length of the array and do the
* swap.
*/
} else {
if (aChar[j] != aChar[i] && j < aChar.length) {
if (aChar[j] == bChar[j]) {
cChar = bChar[j];
bChar[j] = bChar[i];
bChar[i] = cChar;
moves++;
}
cChar = aChar[j];
aChar[j] = aChar[i];
aChar[i] = cChar;
moves++;
} else if (bChar[j] != bChar[i] && j < aChar.length) {
if (aChar[j] == bChar[j]
&& aChar[j] != aChar[i]) {
cChar = aChar[j];
aChar[j] = aChar[i];
aChar[i] = cChar;
moves++;
}
cChar = bChar[j];
bChar[j] = bChar[i];
bChar[i] = cChar;
moves++;
}
}
/*
* At the end, if arrays are equal, then it is done.
*/
if (aChar == bChar) {
break;
}
}
}
}
}
return moves;
}
}
Zaboravio sam u prethodonom kodu da mi je falio jedan brojac pomeranja.
P.S. Ne znam cemu tolika potenciranja nekih algoritama. 100 ljudi, 100 cudi. Ne mora sve da se radi po sablonu koji je neko vec radio.
Pozdrav. [ djoka_l @ 13.10.2014. 13:33 ] @
Za stringove "abcdeaaa", "abccccaaaaa" daje rezultat 9.
Da li možeš da objasniš kako se u 9 koraka stiže do identičnih stringova?
[ olp29 @ 13.10.2014. 14:01 ] @
@djoka_I pa vrlo jednostavno. Ako procitas zadatak, videces uslove koji kazu sledece:
Citat:
Input Format and Constraints:
The first and the second line of the input contains two strings A and B. It is guaranteed that the superset their characters are equal.
1 <= length(A) = length(B) <= 2000
All the input characters are between 'a' and 'z'
Kada ovo procitas shvatices da je to sto si ti napisao nedopustiv unos, kao i da je tvoja pojava vrlo lako kontrolisana i resiva kodom koji mi se nalazi u main metodi:
Code:
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.println("Enter the string A:");
while (!scanner.hasNext("[A-Za-z]+")) {
System.out
.println("Nope, that's not it! Enter the value from \"a\" to \"z\"."
+ "Enter your string A again!");
scanner.nextLine();
}
String a = scanner.nextLine();
a.toLowerCase();
System.out.println("Enter the string B:");
while (!scanner.hasNext("[A-Za-z]+")) {
System.out
.println("Nope, that's not it! Enter the value from \"a\" to \"z\"."
+ "Enter your string B again!");
scanner.nextLine();
}
String b = scanner.nextLine();
b.toLowerCase();
scanner.close();
if ((a.length() >= 1 && a.length() <= 2000) && a.length() == b.length()) {
MinimumStringMoves minimumStringMoves = new MinimumStringMoves(a, b);
System.out.println("Minimum string moves: "
+ minimumStringMoves.findMinimumStringMovement());
}
}
Tako da to sto si ti napisao bi prijavilo gresku i ne bi dozvolilo obradu programa.
Pozdrav. [ blekmor @ 14.10.2014. 01:00 ] @
@olp29
Da li si siguran da ovo rješenje daje zaista najmanji mogući broj koraka? Pogledao sam tvoj metod i nije mi jasno na osnovu čega to možeš da tvrdiš? Jedini korektan odgovor na ovo pitanje je dokaz valjanosti algoritma. Naravno, ne tražim od tebe da mi išta dokazuješ, nego ti skrećem pažnju da jedino uz dokaz možeš biti siguran da ti je rješenje tačno. Možda izgleda kao tačno, ali "izgleda" nije dovoljan argument.
Prekopirao sam tvoj metod i zadao ulazne parametre "abababab" i "aaaabbbb" i tvoj metod kaže da je potrebno 9 koraka. Medjutim, postoji rešenje u 4 koraka:
abababab -> baababab -> baababba -> aaababbb ->aaaabbbb,
što znači ili da tvoje rješenje nije tačno ili da ja nisam dobro prekopirao rješenje (dva puta sam kopirao, isti su mi rezultati) ili da ti nisi dobro kopirao rješenje na forum.
Možda griješim, ali čini mi se da ti je pristup loš.
Citat: olp29:
P.S. Ne znam cemu tolika potenciranja nekih algoritama. 100 ljudi, 100 cudi. Ne mora sve da se radi po sablonu koji je neko vec radio.
Naravno da ne mora. Ne moraš putovati u susjedni grad vozom, tom čudnom aždajom, ako ti neko to predloži. Možeš krenuti hodajući nogama ili rukama. Možeš možda napraviti mašinu za teleport, ili nešto slično. Ali jednom kada odeš vozom, sledeći put ćeš znati kako da prilično efikasno odeš do susjednog grada, bez mnogo razmišljanja. To ne znači da svugdje možeš i trebaš ići vozom (jako mnogo volim vozove), ali da ga uvjek treba imati na umu i znati procjeniti kada ga iskoristiti. Sa druge strane, opterećivanje šablonima uništava kreativnost, tako da treba znati balansirati.
Konkretno, dobio sam ideju kako da rješim problem koji si postavio nakon nekoliko minuta razmišljanja. Nakon toga mi je bilo potrebno još 10ak minuta kako bih u potpunosti rješio problem (bez implementacije). Sa druge strane ti se mučiš sa problemom prilično dugo. To ne znači da sam ja pametniji od tebe. To znači da sam se ja već vozio vozom na toj relaciji i znam gdje je stanica, dok si ti odmah krenuo hodajući, i to, čini mi se, na rukama.
"štuj one koji bili su tu pre tebe, da nije bilo njih, ne bi bilo ni tebe" - Furio Djunta (smajli)
Pozdrav [ djoka_l @ 14.10.2014. 09:13 ] @
Evo i ja da ti predložim kako da testiraš program da bi bio siguran da daje optimalan broj poteza.
Pošto si mi skrenuo pažnju da su ograničenja da su nizovi sastavljeni tako da uvek postoji rešenje, možeš Monte Karlo metodom da uradiš sledeću seriju testova:
1. Generiši slučajan niz znakova dužine n (1 < n < 2000)
2. Generiši slučajan broj m u nekom opsegu recimo (5 < m < 100)
3. Za svako k = 1..m
4.a uradi k slučajnih transformacija nad nizom (zamena mesta susednim članovima, ili prvog i poslednjeg)
5.a nađi broj poteza koji tvoj algoritam vraća.
6.a ako je broj poteza koji je tvoj program pronašao manji ili jednak od k onda je eksperiment uspešan.
7.a ako nije, ispiši početni i krajnji string, da bi kasnije mogao da analiziraš zašto nije nađen najkraći broj koraka
Sve ovo ponavljaj dokle god se za svaki slučajni niz i za svaki broj slučajnih transformacija ne dobije da program nalazi rešenje za manji ili jednak broj koraka u odnosu na broj slučajnih koraka.
Tek nakon nekoliko hiljada eksperimenata možeš da se nadaš da tvoj progrom stvarno možda radi kako treba.
[ olp29 @ 14.10.2014. 10:08 ] @
@blakmor U pravu si. Koliko god da je ovo resenje meni "izgledalo" dobro, zapravo radi samo za odredjen broj slucaja. Kada se prica o valjanosti i sigurnosti da li je neki algoritam tacan ili ne, nakon ovih reci i pregleda ja to ne mogu da tvrdim za moje resenje. Ovo znaci da je moje resenje lose i ne radi u 100% slucajeva i da bi verovatno negde u firmi dobio od QA gomilu stvari da promenim i popravim. Ja nemam bas mnogo vremena u poslednje vreme ali cu poceti da resavam problem tvojim algoritmom, pa ako bas ne ide ja cu ti pustiti PM.
Sto se vozova tice, veoma zivopisno. Hvala. :)
@djoka_I U pravu si. Izvini. Moje resenje nije dobro kao sto napomenuh gore. Trenutno imam nekih obaveza na fakultetu i nekih intervjua, ali se nadam da cu do vikenda nakupiti vremena da krenem da slusam i radim kako je ovde predlozeno. Zato su ovi forumi odlicna stvar, uvek mozes da dobijes drugo ili pak trece misljenje.
Javljam kada i ako odradim nesto.
Pozdrav.
[ blekmor @ 14.10.2014. 16:17 ] @
Bitno je naglasiti poslednju rečenicu koju je napisao djoka_l, da nakon nekoliko hiljada ovakvih eksperimenata možeš da se nadaš da program radi kako treba, ali ne možeš to da kažeš sa sigurnošću. Bitno je naglasiti tu činjenicu, jer se nekome može učiniti da nakon ovakvog eksperimenta može reći sa sigurnošću da mu algoritam radi. Da bi bio siguran da ti algoritam radi, a dokazuješ valjanost ovakvim eksperimentom, moraš ili izlistati sve moguće ulaze i izvršiti eksperiment za svaki mogući broj pomjeranja, ili nekako razbiti skup svih ulaza na klase ekvivalencije ili nešto slično. Izlistavanje svih mogućih ulaza i pomjeranja je prilično vremenski kompleksno, te je pitanje da li se uopšte može uraditi u nekom prihvatljivom vremenskom periodu.
@djoka_l
Druga stvar se tiče samog eksperimenta kojeg si ti napisao.
Ako izvršim k slučajnih transformacija, a moj algoritam mi izbaci rešenje r<=k, to ne znači da je r zaista najmanji mogući broj koraka, odnosno da algoritam radi kako treba.
Primjer:
1.Neka imamo ulaz 12345,
2.Neka je k = 3,
3.Neka se izvrši sledećni slučajan niz pomjeranja : 12345 -> 21345 -> 12345 -> 21354,
4.Neka algoritam rješi problem u r=3 koraka (npr, baš isti niz slučajnih koraka iz 3.)
Rješio si problem za r<=k koraka, ali to ne znači da ti je algoritam našao najmanji broj koraka potrebnih za rešavanje, jer se ovaj ulaz može rješiti sa jednim pomjeranjem.
@olp29
Piši ako budeš imao ikakvih pitanja ili slično
Pozdrav
[ djoka_l @ 14.10.2014. 18:57 ] @
Ja se slažem sa tobom, blekmor, ali uz jednu veliku ogradu!
Pre svega ne volim Monte Karlo metodu. Moj profesor sa faksa je voleo da kaže (pokojni profesor Slavić): čuvajte se Monte Karla, grada i metode!
Međutim, pretpostavi da generišeš niz od 1000 znakova. Koliko treba da napraviš pomeranja, a da dva puta pomeriš isti element (sa verovatnoćom većom od 50%)? Odgovor je 30-35 (odnosno oko 1.2*sqrt(n)).
Dakle, za jako dugačke nizove i mali broj pomeranja, velika je verovatnoća da postoji samo jedno rešenje koje je optimalno i tačno ima broj koraka koliko si ti uradio puta slučajnu permutaciju. Zato sam rekao da će MOŽDA biti siguran POSLE NEKOLIKO HILJADA eksperimenata da je rešenje tačno.
Heuristika, sa druge strane, ne garantuje optimalno rešenje, zato što je prostor stanja ogroman.
Prednost Monte Karla, u ovom primeru, je u tome što možeš da uradiš hiljade AUTOMATSKIH eksperimenata i da ne razmišljaš mnogo o ishodu dokle god dobijaš "dobar" rezultat.
[ olp29 @ 14.10.2014. 19:14 ] @
Znate kako, ja mislim da A* algoritam ne bi pruzio optimalno resenje kao ni bubble sort. Bubble sort bi pravio neka nepotrebna pomeranja. Znas vec o cemu pricam, da ne davim dublje.
Pozdrav.
[ blekmor @ 15.10.2014. 22:21 ] @
@djoka_l
Ne možeš nikako "možda biti siguran", ili si siguran ili nisi. Ako si možda siguran, to znači da nisi siguran. Slažem se sa tobom da je velika vjerovatnoća da ti algoritam radi, ako uradiš eksperiment koji si ti predložio dovoljan broj puta. Poenta je samo u tome da ne možeš biti siguran. No, da ne cjepidlačim više, na istim smo "talasnim dužinama".
@olp29
Nema tu šta da se misli. Očigledno nisi pročitao tekstove koje sam ti poslao u mom drugom odgovoru na ovu temu. A* daje optimalno rešenje ako heuristička funkcija zadovoljava neke uslove.
Oprosti mi ako griješim, ali meni se čini da ti ovde nisi najbolje shvatio zadatak, odnosno šta je to minimalano/optimalano rješenje. Ne traži se da algoritam uradi optimalan broj koraka kako bi našao rješenje, nego da rešenje bude optimalno. To su dvije različite stvari. Optimalnost i efikasnost su dvije različite stvari. Neka je prvi string aba, a drugi string aab i neka algoritam "vrti" sledeće:
aba -> baa -> aba -> baa -> aba -> aab , i neka izbaci rešenje k = 1. Algoritam je uradio šta se od njega traži, odnosno našao je optimalan broj pomjeranja. To što mu je trebalo 5*k koraka kako bi on to izvrtio i zaključio, to nema veze.
Pomislio sam da mješaš ove pojmove zbog toga što si napisao da "babl sort bi pravio neka nepotrebna pomjeranja". Algoritam može da pomjera šta hoće i koliko hoće, ako na kraju izbaci tačno rešenje. Sa druge strane, algoritam koji si ti napisao povećava broj koraka kad god se izvrši neka zamjena, što me takodje navodi na zaključak da nisi baš najbolje suštinski razumio zadatak.
Copyright (C) 2001-2024 by www.elitesecurity.org. All rights reserved.
|