|
begin process at 2008 07 20 02:42:59
Derniers logiciels
|
Trouver une ressource (Nouvelle version du moteur, plus rapide & pertinent, essayez le !)
Vous ne trouvez pas de réponse à votre problème ? Alors posez la question dans le forum.
Souvenez-vous qu'il n'y a jamais de question bête, mais rester dans l'ignorance parce que l'on n'ose pas poser une question, ça c'est une erreur !
Sujet : Cherche algorithme de devinette [ Divers / Général ] (ycochard)
|
Cherche algorithme de devinette
le 01/05/2008 17:54:50

ycochard
|
Bonjour, Je cherche l'algorithme qui se trouve derrière ce petit jeu : http://www.akinator.com/aki_fr/ (attention les yeux, ça flashe) Vous savez comment il s'appelle ? Mes recherches n'ont rien donné :-( Je crois qu'il a une fonction d'amélioration : s'il n'a rien trouvé il demande quelle question il aurait fallu poser, et la réponse qui va avec. Il peut ensuite s'en servir pour mieux deviner. Il est classiquement utilisé pour jouer, pour deviner la personne ou l'objet à laquelle pense le joueur, mais je voudrais l'implémenter pour une fonction d'identification de plantes. Merci Yann
|
|
|
|
Re : Cherche algorithme de devinette
le 02/05/2008 11:01:55

malalam
(Admin CS)
|
Hello,
tu devrais demander à akinator directement. Il y a un lien "contact". Ceci dit, je doute qu'ils partagent... Toujours est-il que leur bidule est impressionnant! Je suis resté sur le cul, pour parler impoliment. J'ai essayé 2 fois et ça a marché les 2 fois, et très vite. Leur algo cerne vraiment vite...vraiment bien foutu. Je suis impressionné lol...
|
|
|
|
Re : Cherche algorithme de devinette
le 02/05/2008 11:07:05

malalam
(Admin CS)
|
En tous cas, ce qui est sûr, c'est qu'ils s'appuient sur une sacrée base de données (3 sur 3 là... : ma copine d'abord, mon chat, puis Teddy Rinner...pour ce dernier je ne pensais pas que le site trouverait...grosse base de données très à jour...nan, décidément, je suis impressioné! Merci pour le lien ;-)).
|
|
|
|
Re : Cherche algorithme de devinette
le 02/05/2008 15:29:17

coucou747
|
quand il te pose une question, j'imagine qu'il pose celle qui te permet d'eloigner le plus de "suspects".
imagine, t'as :
questionX : - R1 - R2 - R3
il y a encore N1 personnes qui correspondent a la reponse R1 (et aux autres questions repondues evidement), N2 pour R2, et N3 pour R3.
plus Max(N1, N2, N3) est petit, plus la question est pertinente (en effet, moins elle laisse de suspects...)
J'ai mis ici des valeurs bool : le personnage correspond il a la reponse R1 : oui ou non, a la reponse R2, oui ou non. Cet algo n'est pas forcement correct parce-qu'on a parfois des gens qui se trompent en entrant quelqu'un.
Ensuite, leur algo n'est peut-etre pas construit comme ca : en effet, tu peux construire un arbre de questions reponses en "live" qui amene a chaque personne : je m'explique : au debut, t'entres une question, et une personne par reponse. C'est ton arbre de depart. Ensuite, chaque fois que le site ne trouve pas la personne, il demande une question supplementaire qu'il ajoute alors a cet emplacement, pour separer son erreur de la vraie reponse.
Cet algo peut-etre sujet, plus facilement, a des doublons et des erreurs par contre.
|
|
|
|
Re : Cherche algorithme de devinette
le 02/05/2008 15:36:08

malalam
(Admin CS)
|
Moi je pense en effet qu'ils fonctionnent plutôt par chemin. Ce qui me fait dire ça, c'est que vers la fin du jeu, quand le site a en fait déjà trouvé, il pose quelques questions totalement hors sujet : je pense qu'il apprend et complète son chemin au fur et à mesure, éloigne les réponses sans rapport. Je pense que c'est une sorte d'arbre, mais un très gros...c'est de la recherche opérationnelle.
|
|
|
|
Re : Cherche algorithme de devinette
le 02/05/2008 15:46:17

coucou747
|
si c'etait un simple arbre, il n'y aurait qu'un chemin de la racine a une personne.
chaque question decrit des ensembles de personnes (ceux qui ont leurs caracteristiques)
je pense que les questions additionelles servent a vraiment faire un graph, quand il ne connait pas le lien entre une personne et une reponse.
|
|
|
|
Re : Cherche algorithme de devinette
le 02/05/2008 15:51:40

malalam
(Admin CS)
|
Un arbre n'implique pas qu'un seul chemin de la racine à la personne. Regarde l'algo su scrabble, je pensais plutôt à un truc de ce genre. Mais ça peuit-être beaucoup de choses en fait...tjrs est-il que l'algo est rapide...mais s'il est rapide c'est parce que la bdd derrière est grosse. Néanmoins, les questions sont très générals au départ, puis se précisent : cela ressemble vraiment à un arbre. mais bon...difficile de savoir.
|
|
|
|
Re : Cherche algorithme de devinette
le 02/05/2008 16:16:45

coucou747
|
je ne sais pas de quel algo tu parles
Personellement, je trouve l'inclusion d'ensemble plus seduisante. (ma premiere idee revient a une inclusion d'ensembles)
|
|
|
|
Re : Cherche algorithme de devinette
le 03/05/2008 05:59:28

coucou747
|
code fait rapidement, a l'arrache, c'est moche, c'est lent, mais ca a le merite de te donner quelques indices
<?php
function newQuestion(){
return '
<input type="text" name="question" value="entrez une question supplementaire ici "/>
<div class="plusmoinsbox">
<input type="button" onclick="add(\'reponsesBox\')" value="+"/>
<input type="button" onclick="del(\'reponsesBox\')" value="-"/>
</div>
<div id="reponsesBox">
<div>
<input type="checkbox" name="is[]" value="ok" />
reponse <input type="text" name="reponse[]" />
</div>
</div>
';
}
function insertName($nom){
$nom=strtolower(htmlentities($nom));
$nom=strtoupper($nom[0]).substr($nom, 1);
$a=mysql_query('INSERT INTO personnes SET nom="'.$nom.'"');
if ($a===false){
$a=mysql_query('SELECT id FROM personnes WHERE nom="'.$nom.'"') or die(mysql_error());
$data=mysql_fetch_assoc($a);
if ($data===false){
echo 'Personne a ce nom !';
return false;
}
$id=$data['id'];
echo $id;
}else{
$id=mysql_insert_id();
}
foreach ($_SESSION['reponses'] as $r){
mysql_query('INSERT INTO link SET id_personne='.$id.', id_reponse='.$r);
}
return true;
}
session_start();
mysql_connect('', '', '') or die(mysql_error());
//met ici tes identifiants de connections...
//mysql_query('DROP DATABASE QuestionsReponses') or die(mysql_error());
mysql_query('CREATE DATABASE IF NOT EXISTS QuestionsReponses') or die(mysql_error());
mysql_query('USE QuestionsReponses') or die(mysql_error());
mysql_query('CREATE TABLE IF NOT EXISTS question(
id int unsigned auto_increment,
question text,
primary key(id)
)') or die(mysql_error());
mysql_query('CREATE TABLE IF NOT EXISTS reponse(
id int unsigned auto_increment,
id_question int unsigned,
reponse varchar(200),
primary key(id)
)') or die(mysql_error());
mysql_query('CREATE TABLE IF NOT EXISTS personnes(
id int unsigned auto_increment,
nom varchar(200),
primary key(id),
unique(nom)
)') or die(mysql_error());
mysql_query('CREATE TABLE IF NOT EXISTS link(
id_personne int unsigned,
id_reponse int unsigned,
unique(id_personne, id_reponse)
)') or die(mysql_error());
echo '
<html>
<head>
<style>
input[type="text"]{
width:80%;
border:0px solid;
border-bottom:1px solid #000;
background: #EEE;
}
.plusmoinsbox{
width:10%;
border:1px solid #AAA;
text-align:center;
margin:10px;
}
#reponsesBox{
width:90%;
border:1px solid #AAA;
margin-left:auto;
margin-right:auto;
padding:10px;
margin-top:10px;
margin-bottom:10px;
}
</style>
<script type="text/javascript">
var counter=1;
function add(id){
var e=document.getElementById(id);
var fc=e.firstChild;
while (fc.nodeName!="DIV") fc=fc.nextSibling;
var clfc = fc.cloneNode(true);
e.appendChild(clfc);
counter++;
}
function del(id){
if (counter==1) return;
var e=document.getElementById(id);
var fc=e.lastChild;
while (fc.nodeName!="DIV") fc=fc.previousSibling;
e.removeChild(fc);
counter--;
}
</script>
</head>
<body>
<form action="questionsreponses.php" method="post">
';
if (!isset($_SESSION['reponses']))
$_SESSION['reponses']=array();
if (!isset($_SESSION['questions']))
$_SESSION['questions']=array();
if (isset($_POST['autre_question'])){
$_SESSION['questions'][]=intval($_POST['idq']);
$_SESSION['questions']=array_unique($_SESSION['questions']);
}else if (isset($_POST['clean'])){
$_SESSION['reponses']=array();
$_SESSION['questions']=array();
}else if (isset($_POST['reponse'])){
if (isset($_POST['question'])){
mysql_query('INSERT INTO question SET question="'.htmlentities($_POST['question']).'"')
or die(mysql_error());
$qid=mysql_insert_id();
$_SESSION['questions'][]=$qid;
foreach ($_POST['reponse'] as $i=>$q){
mysql_query('INSERT INTO reponse SET reponse="'.htmlentities($q).'", id_question='.$qid)
or die(mysql_error());
if (isset($_POST['is'][$i])){
$_SESSION['reponses'][]=mysql_insert_id();
}
$_SESSION['reponses']=array_unique($_SESSION['reponses']);
$_SESSION['questions']=array_unique($_SESSION['questions']);
}
}else if(isset($_POST['idq'])){
$_SESSION['questions'][]=intval($_POST['idq']);
foreach ($_POST['reponse'] as $i=>$on){
$_SESSION['reponses'][]=$i;
}
$_SESSION['reponses']=array_unique($_SESSION['reponses']);
$_SESSION['questions']=array_unique($_SESSION['questions']);
}
}else if (isset($_POST['nom'])){
insertName($_POST['nom']);
}else if (isset($_POST['autre_nom'])){
insertName($_POST['autre_nom']);
}
$List=implode(', ', $_SESSION['reponses']);
$QList=implode(', ', $_SESSION['questions']);
if ($List!=''){
$suspects=mysql_query('
SELECT id_personne, COUNT(*) as count,
(SELECT nom FROM personnes WHERE personnes.id=link.id_personne) AS nom
FROM link WHERE id_reponse IN ('.$List.')
GROUP BY id_personne
HAVING '.count($_SESSION['reponses']).'=count
') or die(mysql_error());
$nombre_suspects = mysql_num_rows($suspects);
}else{
$suspects=false;
$nombre_suspects=-1;
$List='0';
$QList='0';
}
if ($nombre_suspects==1){
$data=mysql_fetch_assoc($suspects);
echo '<p>'.$data['nom'].'</p>
<input type="text" name="autre_nom" value="sinon, qui est-ce ?" />';
}else if ($nombre_suspects==0){
echo '
<input type="text" name="nom" value="qui est-ce ?" />
';
}else{
$req=mysql_query('
SELECT
id, question,
(
SELECT MAX((SELECT COUNT(*) FROM link WHERE id_reponse=reponse.id
AND id_personne IN
(SELECT id_personne FROM link WHERE id_reponse IN ('.$List.') )
/*ici, il manque une notion d\'ordre, c\'est mauvais,*/
/*mais ca devrait fonctionner a peu pres correctement*/
))
FROM reponse
WHERE id_question = question.id
) as max
FROM question
WHERE id NOT IN ('.$QList.')
ORDER BY max DESC
') or die(mysql_error());
if (mysql_num_rows($req)==0){
echo newQuestion();
}else{
$data=mysql_fetch_assoc($req);
echo '<div id="question">'.$data['question'].' ('.$data['max'].')</div>
<input type="hidden" name="idq" value="'.$data['id'].'" />';
$req=mysql_query('SELECT reponse, id FROM reponse WHERE id_question='.$data['id']) or die(mysql_error());
while ($data=mysql_fetch_assoc($req)){
echo '<div class="reponse">
<input type="checkbox" name="reponse['.$data['id'].']" />'.$data['reponse'].'</div>';
}
echo '<input type="submit" value="autre question" name="autre_question"/>';
}
}
echo '
<br />
<input type="submit" value="poster"/>
<br />
<input type="submit" value="effacer mes reponses" name="clean"/>
</form>';
if ($suspects!==false){
$suspects=mysql_query('
SELECT id_personne, COUNT(*) * 100 / '.count($_SESSION['reponses']).' as count,
(SELECT nom FROM personnes WHERE personnes.id=link.id_personne) AS nom
FROM link WHERE id_reponse IN ('.$List.')
GROUP BY id_personne
') or die(mysql_error());
echo '</ul>
<ul id="suspects">';
while ($data=mysql_fetch_assoc($suspects)){
echo '<li>'.$data['nom'].' ('.intval($data['count']).' %)</li>';
}
echo '</ul>';
}
echo '
</body>
</html>
';
?>
|
|
|
Classé sous : fonction, cherche, devinette, algorithme, deviner
|
Téléchargements
Logiciels à télécharger sur le même thème :
|
|